On 3/25/07, June Kim <[EMAIL PROTECTED]> wrote:
http://agcns.com/bentley1.pdf
The thing about Floyd's insertion algorithm is that
it generates random numbers in a sequence, but
the ordering of that sequence isn't random -- it
will tend to have small numbers first.
So you need to use a random permutation to get
things in the right order.
For the case where you're generating just a few
numbers from a long sequence, it's almost always more
efficient to just generate independent random numbers
from that sequence, tossing and repeating to deal
with collisions.
For the case where you're generating the full sequence,
it makes more sense to just use random permutation.
Floyd's insertion approach might have an advantage
where you're generating around half of the sequence,
but it's not clear to me if it has a significant advantage
there. (It does give a clear upper bound on time.)
Anyways, here's a tacit implementation of that algorithm:
another=: 1:`({:@[`([EMAIL PROTECTED])@.({:@[ { ]))`]}
rndmask=: [EMAIL PROTECTED] ([:>[:another&.>/<@(]#0:),~[:(,&.>?@>:)[EMAIL
PROTECTED]) ]
(Perhaps I should break that up into smaller words?)
Here's an obvious speedup for the general case:
rndmask2=: rndmask`(-~ [EMAIL PROTECTED] ])@.(>-:)
Example use:
7 rndmask2 9
0 1 1 1 0 1 1 1 1
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
