Recursive function to develop permutations

[Alex Martelli]

Steve Goldman <steve_g at ix.netcom.com> wrote:

> Hi,
> 
> I am trying to come up with a way to develop all n-length permutations of a
> given list of values.  The short function below seems to work, but I can't
> help thinking there's a better way.  Not being a computer scientist, I find
> recursive functions to be frightening and unnatural.  I'd appreciate if
> anyone can tell me the pythonic idiom to accomplish this.

The implementation of something that is naturally defined recursively is
often simplest when done recursively (unless there's some manual
equivalent of a "tail call optimization" that's easy and natural).  And
many things in combinatorics are generally subject to naturally
recursive definitions.

If you hope to find a natural and smooth non-recursive implementation,
think first about a non-recursive definition (the alternative is putting
the recursion in, then removing it by explicitly introducing a stack; it
works, but is not necessarily pretty).

In this case it seems to me that you're lucky: there IS a non-recursive
definition of "permutations of length N out of a list of X values".  It
may go something like...:
  each result is a container with N slots.  each slot, independently,
  assumes each of the X values, yielding X**N results

This is like saying that (if the X values are digits in base X) the
result is a number counting in base X from 0 to X**N-1.  In fact, the X
values may be arbitrary, but the INDICES of the values in the list that
holds them ARE the numbers 0 to X-1, i.e., exactly the digits in base X.

So, we have reduced the problem to one of counting in an arbitrary base,
so it becomes pretty easy to solve non-recursively.  For example:

def permute(Xs, N):
    permutations = []
    permutation = [None] * N
    X = len(Xs)
    for i in xrange(X**N):
        for j in xrange(N):
            i, k = divmod(i, X)
            permutation[j] = Xs[k]
        permutations.append(list(permutation))
    return permutations

Here, we're using i as an actual count, an integer, and the inner loop
does the 'base expansion' of each i, plus the indexing to replace each
digit with the corresponding item of Xs.

Note that I've called the argument Xs, *NOT* list, because I want to use
the built-in name 'list' for its normal purpose: making a new list
that's a copy of an existing one (I prefer that to such goofy idioms as
permutation[:], permutation+[], or permutation*1, even though they all
do the same job and the last one is a real characters-saver; I think
list(permutation) is more readable, personally).

In general, it's best to avoid shadowing built-in names in a context
where you're likely to want to use the original meaning of the names.

Of course, there ARE other ways to count:

def permute(Xs, N):
    permutations = []
    permutation = [0] * N
    X = len(Xs)
    while True:
        for k in xrange(N):
            permutation[k] += 1
            if permutation[k] < X: break
            permutation[k] = 0
        else:
            break
        permutations.append([Xs[k] for k in permutation])
    return permutations

Here, I need to use a list comprehension (or some slightly more obscure
construct, such as map(Xs.__getitem__, permutation)...) at append time,
to construct the list of items of Xs from the list of indexes ("digits")
which the algorithm naturally generates.  I hold digits in a
little-endian way, btw, simply because it's marginally simpler and you
did not specify any particular ordering for the result.

Each of these solutions can be enhanced by making it into a generator --
remove the permutations=[] at the start, turn the permutations.append
call into a yield statement.  However, you'll have to turn the simple
"print permute(..." into a "print list(permute(..." in your testcase.
No big deal, if you do need a list as a result; it's frequent that what
you want is to LOOP over the result, in which case there's no need to
make it into a list taking memory space all at once.

Are these "counting" solutions any simpler than the recursive one?  I
don't really think so, for a cleanly-implemented recursion (one without
globals and a first-time switch...!-) such as:

def permute(Xs, N):
    if N <= 0:
        yield []
        return
    for x in Xs:
        for sub in permute(Xs, N-1):
            yield [x]+sub

it seems to me this one has a strong simplicity advantage.  However,
considering the "counting" approaches is still instructive.  Take the
second one again: all the counting it does is a += 1 and a check if some
limit is reached that way.  But that's VERY close to the job of an
iterator, so why not try to use an iterator directly instead of that
"digit in base X"/"index into Xs" number...?  Python generally prefers
iterating directly over values, rather than over digits...

def permute(Xs, N):
    state = [iter(Xs) for k in xrange(N)]
    permutation = [s.next() for s in state]
    while True:
        yield list(permutation)
        for k in xrange(N):
            try: permutation[k] = state[k].next()
            except StopIteration:
                 state[k] = iter(Xs)
                 permutation[k] = state[k].next()
            else:
                 break
        else:
            break

A bit cutesy, perhaps, particularly with the two "else: break" back to
back (one for the try statement breaking out of the for, one for the for
statement breaking out of the while).

And so on, and so forth.  There's hardly any limit to the fun one can
have exploring such problems.

But, for simplicity, recursion is still hard to beat;-).


Alex