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

["David Rudel fwqhgads@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>]

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.