[Edit: For some reason this old post gets much traffic. Please note that Wikipedia has a much nicer presentation (but more verbose) of the Fisher–Yates shuffle.]
While browsing SGB I found a piece of code that looked especially nice. How would you generate a random permutation? That is, an array of size $n$ that contains a shuffle of $0$, $1$, $\ldots$, $n-1$. All orders should be equally probable. It's a nice exercise to try to do by yourself.
The solution in SGB takes linear time and is easy to code:
#include <stdlib.h> int* random_permutation(int n) { int *p = malloc(n * sizeof(int)); for (int i = 0; i < n; ++i) { int j = rand() % (i + 1); p[i] = p[j]; p[j] = i; } return p; }
Do you see why it works?
At (beginning of) step $i$ the array $p[0.\,.\, i-1]$ contains a permutation of the numbers $0.\,.\, i-1$. How can you construct in the array $p[0.\,.\,i]$ a permutation of $0..i$? Choose a random location to put $i$ and save the old value in that location at $p[i]$. If you think about it, this is pretty much a recursive solution. So, a nice problem is: how would you write it in a functional language?
PS: This implementation is not quite OK, because rand() % k
is not uniformly distributed.
7 comments:
I use sort with a random comparation. Works fine for me.
(* return -1 or 1 *)
(* Random.int 2 returns 0 or 1 *)
let random_compare a b =
if Random.int 2 = 0 then -1 else 1
Array.sort random_compare res;
Interesting idea.
Your code looks nice and small and (with high probability) is fast enough in practical situations. But when you think about what is happening beneath.. it's not _that_ nice anymore. For one thing it is O(n lg n) instead of O(n).
Anyway, by "functional" I really meant "without side-effects". Your code uses an array and can be immediately mirrored in a more classical language like C++:
bool random_compare(int a, int b)
{ return rand() % 2; }
sort(res.begin(), res.end(), random_compare);
Please, return p;
@Fiktor: Thanks, fixed.
The reason you get so much traffic is because it is the first hit on Google: "C++ random permutation"
You need to initialize your vector p so that p[i] = i. No?
Anastasios
@Anastasios: The loop body only relies on $0..i-1$ to be non-garbage. So, initially the whole array could be garbage.
Post a Comment
Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.