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

Subject: Re: [xsl] How to Do Random "Shuffle"?
From: "Eliot Kimber ekimber@xxxxxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>
Date: Sat, 13 Sep 2014 15:37:08 -0000
Interesting--thanks for finding the reference (I was focusing my search on
XSLT stuff).

In my case the number of items to be sorted will be small, probably never
more than 10, so efficiency is not that much of a concern at the moment,
but of course this technique could get applied to larger sets (e.g.,
shuffling a large set of test questions, not just the answer options
within a question.

My challenge now is how to generate numbers between the limits: my math
skills are sufficiently bad that I'm not thinking of any immediate
solution.

My hack, which works, is to generate random integers between 1 and 10 and
simply see if, on each iteration, I get a hit on the current list. If I
do, I shuffle and recurse. If I don't, I change the seed and try again.
That should be guaranteed to finish but it's obviously wasteful.

So having a built-in permute() function would be quite helpful for this
particular problem.

For the general task of rendering tests from question markup, randomizing
both the questions and the answer options is general requirement.

I suppose one could also implement this as a custom sort and handle it at
the Java level, but I'd rather avoid any kind of Java extension dependency.

Cheers,

E.
bbbbb
Eliot Kimber, Owner
Contrext, LLC
http://contrext.com




On 9/13/14, 10:18 AM, "Michael Kay mike@xxxxxxxxxxxx"
<xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:

>What you describe is essentially the Fisher-Yates algorithm,
>
>https://en.wikipedia.org/wiki/FisherbYates_shuffle
>
>which strikes me as so obvious I find it surprising it has a name. (Who
>knows, it might even have a patent...)
>
>The challenge is to do it efficiently, which depends on the time
>complexity of the remove() function. If remove() is O(n) (i.e. if it
>involves copying all the items other than the one that's removed), then
>the shuffle is O(n^2).
>
>By contrast, sorting on a random sort key might well be O(n log n).
>
>I've recently proposed a family of random number functions for XPath 3.1,
>and I included permute() as a primitive on the theory that a native
>implementation might be considerably more efficient than a user-written
>implementation.
>
>Michael Kay
>Saxonica
>mike@xxxxxxxxxxxx
>+44 (0) 118 946 5893
>
>
>
>
>On 13 Sep 2014, at 15:29, 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

Current Thread