How would I efficiently generate a random permutation?

First, I am assuming that we need a random permutation of N numbers 0 to N-1. If not, then we can probably map the problem to such a form. I saw a brilliant algorithm for doing exactly this in the book Programming Pearls by Jon Bentley which in turn is based on Knuth's Algorithm P in section 3.4.2. The pseudocode is surprisingly simple - Given an array having integers from 0 to n-1 for i = [0, n)     swap(i, randint(i, n-1)) In C++, this would look something like int *x = new int[n]; // Initialize the array for(int i = 0; i < n; ++i) { x[i] = i; } for(int i = 0; i < n; ++i) { int j = randint(i, n-1); int temp = x[i]; x[i] = x[j]; x[j] = temp; } Edit: As mentioned above, this is equivalent to Fisher-Yates Shuffle and is also known as the Knuth Shuffle.

If you wanna know about the algorithm take a look at Fisher-Yates Shuffle. Following is the code in python, from itertools import permutations for string in permutations("abcde"): print string #or do what ever. eg:Appending It gives, ('a', 'b', 'c', 'd') ('a', 'b', 'd', 'c') ('a', 'c', 'b', 'd') ('a', 'c', 'd', 'b') ('a', 'd', 'b', 'c') ('a', 'd', 'c', 'b') ('b', 'a', 'c', 'd') ('b', 'a', 'd', 'c') ('b', 'c', 'a', 'd') ('b', 'c', 'd', 'a') ('b', 'd', 'a', 'c') ('b', 'd', 'c', 'a') ('c', 'a', 'b', 'd') ('c', 'a', 'd', 'b') ('c', 'b', 'a', 'd') ('c', 'b', 'd', 'a') ('c', 'd', 'a', 'b') ('c', 'd', 'b', 'a') ('d', 'a', 'b', 'c') ('d', 'a', 'c', 'b') ('d', 'b', 'a', 'c') ('d', 'b', 'c', 'a') ('d', 'c', 'a', 'b') ('d', 'c', 'b', 'a')