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

["Wolfgang Laun wolfgang.laun@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>]

Most likely, I'd generate a permutation using an easy way and pass it in as
a parameter. Or call Java's Collections.shuffle, if that's an option.

And: yes, I'm lazy.
-W

On 13 September 2014 17:37, Eliot Kimber ekimber@xxxxxxxxxxxx <
xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:

> 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.
> ----------
> 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/Fisher-Yates_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
> >> ----------
> >> Eliot Kimber, Owner
> >> Contrext, LLC
> >> http://contrext.com