Re: [xsl] How to Do Random "Shuffle"?

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