Subject: Re: [xsl] How to Do Random "Shuffle"? From: "David Rudel fwqhgads@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> Date: Thu, 18 Sep 2014 12:05:13 -0000 |
Wolfgang, the same type of weakness will appear in pretty much any version of this algorithm. And I suspect that the above is actually less susceptible to such bizarre cases than other algorithms because only one sequence is calculated rather than many. In any event he random:random-sequence function provides values to 64-bit precision, so the likelihood that a problem arises is practically 0. The probability that two random values in a sequence are equal is less than n^2 / 2 * precision, so you would have to have an N of about a 1,000,000,000 before any significant probability of error (about a 3% chance) You could always do a check on count(distince-values($rand)) if you were really worried about it, but unless your code is meant to navigate nuclear weapons, I doubt such a step is necessary. On Thu, Sep 18, 2014 at 1:48 PM, Wolfgang Laun wolfgang.laun@xxxxxxxxx <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: > What if the unsorted sequence is (0.413,0.192,0.888,0.513,0.522,0.413)? > > Admittedly, given existing implemenations of random generators for doubles > in [0,1.0), this is rather unlikely, but you may have a hard time proving > that it is impossible. > > -W > > > On 18 September 2014 13:35, David Rudel fwqhgads@xxxxxxxxx > <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: >> >> That is not what random:random-sequence does. It creates a sequence of >> N random numbers between 0 and 1. >> >> But if you then find the index of each of these numbers in the sorted >> version of this sequence, **then** you have created a random >> permutation of the numbers from 1 to N, as the OP requested. >> >> So, by way of example, let's say random:random-sequence(5) spits out >> (0.413,0.192,0.888,0.513,0.522) >> >> Then the sorted version is (0.192,0.413,0.513,0.522,0.888). >> >> Taking each element (in sequence) from the original output of >> random:random-sequence() and finding the index in the sorted sequence >> yields (2,1,5,3,4), a random permutation of the numbers from 1 to 5. >> >> >> On Thu, Sep 18, 2014 at 1:14 PM, Wolfgang Laun wolfgang.laun@xxxxxxxxx >> <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: >> > random:random-sequence(N) >> > >> > If this is supposed to produce a sequence of numbers in the range 1..N >> > while >> > expecting it to contain every number of that range exactly once: would >> > this >> > truly be a "random" sequence? I don't think so. >> > >> > -W >> > >> > >> > >> > On 18 September 2014 11:05, David Rudel fwqhgads@xxxxxxxxx >> > <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: >> >> >> >> When I have to do this (essentially create a permutation of the numbers >> >> from 1 to N), I combine random:random-sequence with saxon:sort >> >> >> >> I'm away right now so I'm not working on a machine with XSLT, so the >> >> following syntax may be off, but I use: >> >> >> >> <xsl:variable name="rand" select="random:random-sequence(N)"/> >> >> >> >> <xsl:variable name="sorted.rand" select="saxon:sort($rand)"/> >> >> >> >> <xsl:variable name="permutation" >> >> select="$rand!index-of($sorted.rand,.)"/> >> >> >> >> The select attribute of the last can also be written as "for $i in >> >> $rand >> >> return index-of($sorted.rand,$i)" . >> >> >> >> >> >> On Saturday, September 13, 2014, Eliot Kimber ekimber@xxxxxxxxxxxx >> >> <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: >> >>> >> >>> Using XSLT 2 I need to implement rendering of "match table" questions >> >>> where you have two sets of items, the match item and the thing it >> >>> matches >> >>> to. I want to present this as a literal table, where the first column >> >>> is >> >>> the match-from items in source order and the second column is the >> >>> match-to >> >>> items, in random order. >> >>> >> >>> I think this is best characterized as a "shuffle" problem, where you >> >>> want >> >>> to reorder a list randomly but all items in the list must be accounted >> >>> for. >> >>> >> >>> I can think of a recursive algorithm: given a list, generate a random >> >>> integer between 1 and the list length, select that item and add it to >> >>> the >> >>> result list, then call this function on the original list minus the >> >>> node >> >>> you just selected. >> >>> >> >>> Is there an easier or more efficient way to do it? >> >>> >> >>> Thanks, >> >>> >> >>> Eliot >> >>> bbbbb >> >>> Eliot Kimber, Owner >> >>> Contrext, LLC >> >>> http://contrext.com >> >>> >> >>> >> >> >> >> >> >> -- >> >> >> >> "A false conclusion, once arrived at and widely accepted is not >> >> dislodged >> >> easily, and the less it is understood, the more tenaciously it is >> >> held." - >> >> Cantor's Law of Preservation of Ignorance. >> >> XSL-List info and archive >> >> EasyUnsubscribe (by email) >> > >> > >> > XSL-List info and archive >> > EasyUnsubscribe (by email) >> >> >> >> -- >> >> "A false conclusion, once arrived at and widely accepted is not >> dislodged easily, and the less it is understood, the more tenaciously >> it is held." - Cantor's Law of Preservation of Ignorance. >> > > XSL-List info and archive > EasyUnsubscribe (by email) -- "A false conclusion, once arrived at and widely accepted is not dislodged easily, and the less it is understood, the more tenaciously it is held." - Cantor's Law of Preservation of Ignorance.
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] How to Do Random "Shuffle, Wolfgang Laun wolfga | Thread | Re: [xsl] How to Do Random "Shuffle, Wolfgang Laun wolfga |
Re: [xsl] How to Do Random "Shuffle, Wolfgang Laun wolfga | Date | Re: [xsl] How to Do Random "Shuffle, Wolfgang Laun wolfga |
Month |