Actionscript Permutation Generator

For those of you who just need a permutation generator:
Actionscript 3.0 Permutation Utility class
Actionscript 2.0 Permutation Utility class

Onward…

Some time ago on a tech interview website discussion, we were challenged with the following problem:

Given a number N generate all the permutations e.g. N=3
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2

How to generate the N! permutations efficiently ?

The following is a permutation generator using the factoradic number system. This technique correlates permutations to a lexicographical index. For those of you interested in this kind of thing, I’ve written a brief description of the steps of the algorithm which traces all permutations of n, and included an unoptimized version to further articulate the technique.

You will need a function which computes factorials.

function factorial(i:uint):Number {
	if(i>1) return i*factorial(i-1);
	return 1;
}

Pick n.
Get factorial of order n and assign it to kLen.
Reduce kLen and assign it to k for kth permutation of order n.
Once we have the factoradic of k, we can derive kth permutation of n by increasing each element of r by 1 if elements computed leading up to p are less than p.
In this algo though, we increase r[i] for each element greater than r[p] while computing the factoradic of k. This is an optimization to avoid additional loop to compute factoradic.

var n:uint = 3, kLen:uint = factorial(n);
var r:Array, j:uint, i:uint, p:uint, k:uint;
while(kLen--){
	r = [], j = 1, k = kLen;
	r[n-1] = 0;
	while(j++<n){
		p = i = n-j;
		r[p] = uint(k/=(j-1))%j;
		while(i++<n)
			if(r[i] >= r[p])
				++r[i];
	}
	trace(r);
}

here is the unoptimized version which gets kth permutation of n

var n:uint = 3, k:uint = 6;
//determine factoradic of k
var factoradic:Array = [0];
for(var j:uint = 1;j++<n;){//start to create factoradic
	//get rid of last remainder to move on to next radix
	k = k/(j-1);
	//mod j so element is radix j
	factoradic.unshift(k%j);
}
 
//derive permutation from factoradic
var r:Array = factoradic.slice(), m:uint = 1;
while(m++<n){
	var i:uint = n-m;
	while(i++<n)
		if(r[i] >= r[n-m])
			++r[i];
}
 
trace(r);