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(_at_)saxonica(_dot_)com
+44 (0) 118 946 5893
On 13 Sep 2014, at 15:29, Eliot Kimber ekimber(_at_)contrext(_dot_)com
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> 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
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--