[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

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


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