## A simple and fast permutation generator (7)

*February 29, 2008 at 2:38 pm* *
3 comments *

You know what’s weird? It was right in front of me, but I didn’t make the connection. If you look at part 4 of this series, you can see that the runtime order formula was : ~2,718281828 N!

Dude, 2,718281828… that’s e.

A colleague of mine had to point that out to me ( thanks xtofl 😉 )

Pretty amazing to see that little magic number pop up in this subject. I mean, with the number pi , you can at least see that it has to do with a circle and its circumference, and that almost always explains how pi pops up in formulas. But with e, this is less clear. Less clear to me, that is. The average mathematician will probably think nothing of this result.

Hopefully more on this later, but I can guarantee absolutely nothing.

Any help here would also be greatly appreciated.

Entry filed under: Command Line.

1.Peter Lund | December 21, 2009 at 10:37 pmRandom permutations are easy to do in linear time. Knuth spends a couple of pages on it in The Art of Computer Programming.

This is basically it:

for (i=1 to n) ar[i] = i;

for (i=1 to n) swap(ar[i], ar[Random(i,n)]);

// ar[] here is 1-based

// Random(i,n) is a random integer i <= x <= n

// swap(a,b) must work even if a=b

Explanation in 3 easy steps:

1) You have a bunch of numbers you haven't used yet and an array you would like to fill with your permutation. You start at the first position in the array and grab a random unused number from the pool and plonk it in. Then you do the same at the next position until the entire array is filled in (and there are no more unused numbers). This is O(n) if we can track the unused pool in constant time.

2) let's try and use a single array for both the unused numbers and the final permutation. Let's say we keep the permutation we have built so far in the low positions and the unused numbers in the high positions. For each position we grab a random unused number and then /shrink/ the unused pool by copying entries from lower positions to higher ones to fill in the gap left by the number we used. This is O(n²) but we'll fix that in step 3.

3) let's be a bit smarter about shrinking the unused pool. We don't care about the order in the pool since we just grab a random element at a time. How about taking the number that "stands in the way" for the newly chosen random number at the lower end of the pool/upper end of the permutation and put that number into the "hole" left by the randomly chosen number? In other words, swap the two numbers?

See? Completely linear, two lines of code, no fancy data structures, nothing that's hard to analyze, as easy to write in C++ as it is in Fortran or assembly.

Granted, the memory hierarchy is a bit of a problem: each "turn" is "O(1)" but the random read of the array can vary 200x in cost due to cache misses. It is even worse if we try to do this on files.

2.qbziz | December 21, 2009 at 11:53 pmYou are generating one random permutation, and indeed, this can be done in linear time.

As far as I can tell, this is what the recursive algorithm is doing as well, although it is not generating random permutations.

But the problem was generating all permutations. If you want to generate all permutations of a series of items, you are pretty much bound to the factorial of the number of items.

However, that is nothing to be amazed at. It’s like saying that if you want to visit every element in a list, that you are bound to linear time.

Also if you want to generate all permutations – once – and not just one random permutation , you need to track which ones you have already generated. That won’t work by using a function that returns a random number.

3.Peter Lund | December 24, 2009 at 5:08 amIn that case, I’m sorry, I misunderstood you. Yes, of course generating all permutations is (at least) factorial since the number of permutations is factorial in the number of items. The bookkeeping is not too hard so it doesn’t get worse than factorial.