Steady as a rock

To my shock, I didn’t find a way to enumerate all permutations of a set of items in any reasonably standard python module. (aka installed when I found out on the train). Of course this has been implemented many times before but I’m sharing it anyway :)
A set of n items has n! permutations. Simple factorial implementation (seems also nowhere to be found in the standard python libs or numpy):

def factorial(x):
    if x < 0:
        raise ValueError("Factorial is only defined for x >= 0")
    y = 1
    while x >= 2:
        y *= x
        x -= 1
    return y

Permutations can easily be defined recursively, but that limits you to sets of 1000 items (maximum recursion depth). So better to make an iterative function. Even better: instead of returning a list, use a generator so you don’t have to copy an array many times. This is also a perfect example of writing obfuscated code in a clean language like python.

def permute(items, i):
    items = items[:]
    n = len(items)
    m = factorial(n)
    while n:
        c = (i%m) * n / m
        yield items[c]
        items.pop(c)
        m /= n
        n -= 1

Example:

>>> import permute
>>> items = [1,2,3]
>>> for i in range(permute.factorial(len(items))):
...     print list(permute.permute(items, i))
...
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]