|Perl: the Markov chain saw|
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?