08 April 2005

Random permutation

[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.

8 comments:

Mattias said...

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;

rgrig said...

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);

natalie said...

Good reading

Fiktor said...

Please, return p;

rgrig said...

@Fiktor: Thanks, fixed.

Anonymous said...

The reason you get so much traffic is because it is the first hit on Google: "C++ random permutation"

Anonymous said...

You need to initialize your vector p so that p[i] = i. No?

Anastasios

Radu Grigore said...

@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.