Shuffle

Bill Baxter dnewsgroup at billbaxter.com
Fri Jan 25 03:15:44 PST 2008


Oskar Linde wrote:
> Walter Bright wrote:
> 
>>     /* Shuffle the files[] array
>>      */
> 
> To be nitpicky, your algorithm will not give a perfect shuffling. 
> Consider shuffling the sequence 012. The algorithm has 3^3 = 27 
> different ways it can shuffle the sequence, and there exists 3! = 6 
> different permutations of the sequence. Since 27 isn't divisible by 6, 
> the algorithm will give a slight bias towards some end sequences. 
> (021,102 and 120 in this case). A quick fix is to change the first line 
> of the loop body:
> 
>>     for (size_t i = 0; i < files.length; i++)
>>     {
>>     auto j = std.random.rand() % files.length;
> 
>       auto j = std.random.rand() % (files.length - i) + i;
> 
>>     // swap [i] and [j]
>>     auto tmp = files[i];
>>     files[i] = files[j];
>>     files[j] = tmp;
>>     }
> 
> (the last iteration will be a nop, so the loop condition could be 
> changed into i < files.length-1)

Yep, this is a classic problem from homeworks sets for algorithms 
classes.  How to make a random permutation of N elements in O(N) time 
and O(1) additional space such that every element is equally likely to 
end up in any slot.  And the answer is what Oskar said.    Walter, your 
MechE background is showing. :-)

--bb


More information about the Digitalmars-d-announce mailing list