Subject: Re: [xsl] How to Do Random "Shuffle"? From: "Wolfgang Laun wolfgang.laun@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> Date: Thu, 18 Sep 2014 12:27:38 -0000 |
We aren't talking about the same thing, I think. I'm inclined to follow abstract principles and refuse an approach based on pragmatic approximations. The task of shuffling n distinct objects is fundamentally different from the proposed supposedly equivalent task of pulling n such objects out of a random process. Just go to Las Vegas, or Monte Carlo and see how you can produce a permutation of 0..36 from the results of any table. I'm not sure where the algorithm you are referring to ("64 bit precision") is defined, but I do know, for instance, that Java composes a 52 bit mantissa for a random double from parts(!) of two successive random integers of 32 bit. All right, we're not into SIL-4 or higher. If someone is willing to try their luck, OK, but let's not forget that it isn't exact math. -W On 18 September 2014 14:05, David Rudel fwqhgads@xxxxxxxxx < xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: > 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 > >> >>> ---------- > >> >>> 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, David Rudel fwqhgads | Thread | [xsl] Is the semantics of the "or" , Costello, Roger L. c |
Re: [xsl] How to Do Random "Shuffle, David Rudel fwqhgads | Date | [xsl] Unit Testing, Bertrand Lefort blef |
Month |