To get around this, don't search left and right if you hit a bit that's already been chosen. Just keep choosing and choosing randomly until you hit an unselected bit. With nonzero probability you will terminate ;) This is the only way to choose a permutation truly at random (other than filtering out (or bookkeeping) the unselected bits and randomly picking from them).
Another approach which still builds the entire list, but you may still appreciate because it needs only one call to rand is this: If you look at the swaps made in the Fisher-Yates shuffle, you can build a 1-to-1 mapping from the swaps you performed to the integers between 1 and N!. This is a ranking function, and it induces an ordering over the permutations. An unranking function just does the inverse, converts a number between 1 and N! into the swaps needed to build the permutation:
In other words, this converts the uniform random distribution over the integers from 1 to N! into the uniform random distribution over permutations of N. Ranking/unranking functions is a standard way to select combinatorial structures uniformly at random using just one call to rand (compare to F-Y shuffle, which needs N calls to rand to return a random permutation). Usually you rank/unrank to the standard lexicographic ordering, but in the case of permutations, the ordering induced by the F-Y shuffle actually lets you rank and unrank faster.sub unrank { my ($n, $rank) = @_; my @perm = (0 .. $n); my @swap; for (reverse 2 .. $n) { $swap[$_] = $rank % $_; $rank = int($rank / $_); } for (2 .. $n) { @perm[ $swap[$_], $_ ] = @perm[ $_, $swap[$_] ] if $swap[$_]; } return @perm[1 .. $n]; }
You could try to unravel this unranking function so that it doesn't build the list in memory. In other words, given the rank r of a permutation in some ordering, and an index i, what is the i-th position of the r-th permutation? I'm not sure it's possible with this ordering, but perhaps in a lexicographic ranking/unranking scheme it would be.
For the record, I got a lot of this information about ranking and unranking permutations from the online book Combinatorial generation, which has lots of interesting algorithmic material relating to permutations, combinations, subsets, trees, partitions, etc. Specifically look at the section of chapter 4 relating to permutations (and exercise 23).
Update: I wrote this, ran off to class, and in the middle of lecture realized my unrank function was a bit off.. It's fixed now ;)
blokhead
In reply to Re: Generating 0 .. N Randomly and Efficiently
by blokhead
in thread Generating 0 .. N Randomly and Efficiently
by Limbic~Region
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |