Subject: Re: [xsl] How to Do Random "Shuffle"? From: "Dimitre Novatchev dnovatchev@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> Date: Sat, 13 Sep 2014 17:01:50 -0000 |
On Sat, Sep 13, 2014 at 8:18 AM, Michael Kay mike@xxxxxxxxxxxx <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote: > 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). There doesn't need to be any remove() operation. The random permutation can be built as a new sequence, adding a new item at a time. If the append() operation can be performed in constant time (as I believe is the case with Saxon), then the total computational complexity is O(n * O(generate-random-number)). In case an implementation performs appending to a sequence in O(N), then it can pre-pend to a sequence in constant time -- the result will be the reversed random sequence that would have been produced by appending -- that is also a random sequence. -- Cheers, Dimitre Novatchev --------------------------------------- Truly great madness cannot be achieved without significant intelligence. --------------------------------------- To invent, you need a good imagination and a pile of junk ------------------------------------- Never fight an inanimate object ------------------------------------- To avoid situations in which you might make mistakes may be the biggest mistake of all ------------------------------------ Quality means doing it right when no one is looking. ------------------------------------- You've achieved success in your field when you don't know whether what you're doing is work or play ------------------------------------- To achieve the impossible dream, try going to sleep. ------------------------------------- Facts do not cease to exist because they are ignored. ------------------------------------- Typing monkeys will write all Shakespeare's works in 200yrs.Will they write all patents, too? :) ------------------------------------- I finally figured out the only reason to be alive is to enjoy it.
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] How to Do Random "Shuffle, Abel Braaksma (Exsel | Thread | Re: [xsl] How to Do Random "Shuffle, Dimitre Novatchev dn |
Re: [xsl] How to Do Random "Shuffle, Dimitre Novatchev dn | Date | Re: [xsl] namespace problem, Ruud Grosmann r.gros |
Month |