[**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:

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

Good reading

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.