## Permutation or a time zip?

The title does make sense because it’s an anagram of “premature optimization”. (Found via Xworder , of course).

Permutation generation is another combinatorial algorithm that is NOT used in Xworder. Same story as with powersets (see prev. post). But unlike with powersets, with permutations I didn’t even try to write a fancy algorithm that recurses over enumerators. I prematurely resorted to the good old iterative algorithm shown below (I think it’s due to Knuth). BTW, here is a really really cool post (in a really really cool blog) about efficient recursion in functional programming http://community.bartdesmet.net/blogs/bart/archive/2009/11/08/jumping-the-trampoline-in-c-stack-friendly-recursion.aspx . Unfortunately, I lack brain power to fully understand it 😦

Anyway, here is the permutation algorithm (you need to start with 1, 2, 3, …, n):

private bool NextPermutation(int[] values) { int n = values.Length; int i = n - 1; while (i > 0 && values[i - 1] >= values[i]) i--; if (i == 0) return false; int j = n; while (values[j - 1] <= values[i - 1]) j--; Swap(values, i - 1, j - 1); i++; j = n; while (i < j) { Swap(values, i - 1, j - 1); i++; j--; } return true; }

## Leave a Reply