### Re^2: Random Math Question

by sk (Curate)
 on Oct 11, 2005 at 05:43 UTC ( #499036=note: print w/replies, xml ) Need Help??

in reply to Re: Random Math Question

blokhead, Thanks for all the wonderful explanations.

Let's for this discussion assume that all we need is an algorithm that can potentially produce every p! permutation of a sequence (1..p)

I was wondering whether a two dimensional shuffling (not sure if that is the right term) would help us achieve such a suffle without having to resort to a random variable with entropy 1516705 bits. Here are the steps i have in mind -

1. Partition the sequence into k-lists (each list containing n-elements) and that each list can be truly randomized. Also WLOG let's assume k <= n

2. For all i 1 to n and j = 1 to k,

a. generate integers (X,Y) ~ U from the planar region bounded by x = n and y = k.

b. Now we swap element(i,j) with element(X,Y).

Since each (i,j) is equally likely => i*n+j is equally likely. Is there anything wrong with this approach?

Thanks,

cheers

SK

Create A New User
Node Status?
node history
Node Type: note [id://499036]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (7)
As of 2017-06-24 04:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (556 votes). Check out past polls.