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 11:48:36 -0000
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.

Current Thread