Subject: Re: [xsl] How to Do Random "Shuffle"? From: "Michael Kay mike@xxxxxxxxxxxx" <xsllistservice@xxxxxxxxxxxxxxxxxxxxxx> Date: Sat, 13 Sep 2014 15:18:36 0000 
What you describe is essentially the FisherYates algorithm, https://en.wikipedia.org/wiki/FisherYates_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 userwritten implementation. Michael Kay Saxonica mike@xxxxxxxxxxxx +44 (0) 118 946 5893 On 13 Sep 2014, at 15:29, Eliot Kimber ekimber@xxxxxxxxxxxx <xsllistservice@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 matchfrom items in source order and the second column is the matchto > 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
Current Thread 


< Previous  Index  Next > 

[xsl] How to Do Random "Shuffle"?, Eliot Kimber ekimber  Thread  Re: [xsl] How to Do Random "Shuffle, Eliot Kimber ekimber 
[xsl] How to Do Random "Shuffle"?, Eliot Kimber ekimber  Date  Re: [xsl] How to Do Random "Shuffle, Eliot Kimber ekimber 
Month 