Simple Permutations in Python and Ruby

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

On the way to solving Project Euler problem 24 I came up with a simple recursive function for generating permutations of a simple list (or list-like) object. Check it out:

def permutations(li):
""" Return all permutations of a given list.  This function 
assumes every element of the list is unique. """
if len(li) <= 1:
yield li
else:
for el in li:
for p in permutations([e for e in li if not e == el]):
yield [el] + p

Usage:

>>>for p in permutations('abc'): 
...  print p

['a', 'b', 'c']
['a', 'c', 'b']
['b', 'a', 'c']
['b', 'c', 'a']
['c', 'a', 'b']
['c', 'b', 'a']

The most important thing to recognize is that this is a generator, so it produces only as many results as are required. That is, instead of a method that produces every permutation, perhaps accumulating to a list of results, and then displays all results at once, this function produces one result at a time. The huge payoff is that if I want to find the first n permutations of a long sequence, I don't have to waste time producing all permutations even though I only need the first few. Another bonus: because the list is passed to the function in lexicographic order, permutations are produced in lexicographic order. Just for fun (and to test my burgeoning Ruby chops) here's the rough equivalent in Ruby:

def permutations li
if li.length < 2
yield li
else
li.each do |element| 
permutations(li.select() {|n| n != element}) \
{|val| yield([element] << val)}
end
end
end

It can be called in essentially the same way:

>>>permutations(['a','b','c']) do |n| 
...  puts
...  print n
...end

abc
acb
bac
bca
cab
cba

The only real difference is that rather than passing a generator out of permutations, I pass a block of code in. In proper coroutine style, the external block is executed at every yield statement on the top level (on the original call) and the recursive block (line 7) is used to accumulate values from descendant calls into a complete permutation. Additionally, the Python version will accept any sequence that supports x for x in sequence style list comprehension and always returns lists. The Ruby version (as far as I can tell) only takes arrays and always returns arrays.

Enjoy!