On Sat, Sep 13, 2014 at 8:18 AM, Michael Kay mike(_at_)saxonica(_dot_)com
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> 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.
--~----------------------------------------------------------------
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
--~--