Permutation Generator

[Tom Anderson]

On Mon, 15 Aug 2005, Matt Hammond wrote:

> Just satisfied my curiosity wrt this problem, so I might as well share :-)
>
>>>> def permute(list):

How about:

def permutation(l, i):
 	"Makes the ith permutation of the sequence l."
 	# leave out the reverses if you don't care about the order of the permutations
 	l_ = []; l_[:] = l; l_.reverse()
 	m = []
 	for j in xrange(len(l_)):
 		m.append(l_.pop((i % len(l_))))
 		i = i / (len(l_) + 1)
 	m.reverse()
 	return m

def factorial(n):
 	if (n == 1): return 1
 	else: return n * factorial((n - 1))

def permute(l):
 	for i in xrange(factorial(len(l))):
 		yield permutation(l, i)

>>> for o in permute([1,2,3]): print o
...
[1, 2, 3]
[1, 3, 2]
[2, 3, 1]
[2, 1, 3]
[3, 1, 2]
[3, 2, 1]

The thing i like about doing it this way is that you can use 
permutation(l, i) to make arbitrary permutations on their own, should you 
ever need to do that.

Also, it gives you an easy way to make only the even permutations of a 
list - just feed even numbers into permutation(l, i) (i think!). This 
could be useful if you wanted to build an alternating group for some 
obscure discrete mathematics purpose.

tom

-- 
The future is still out there, somewhere.