Recursive function to develop permutations

[Steve Goldman]

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.

Thanks for your help,

Steve Goldman

###START CODE###

def permute(list,n,initialize=True):
"""A recursive function that returns a list of all length n ordered
permutations of "list", length k."""
if initialize:
global permutation, permutation_list
permutation=[] #This list holds the individual permutations. It
is built one element at a time
permutation_list=[] #This list is the list that will contain all
the permutations
n=n-1 #This counts down for each element of the permutation. It is a
local variable,
#so each subsequent function call has n reduced by one
for e in list:
permutation.append(e)
if n>0: #that is,the permutation needs additional elements
permute(list,n,False)
else: # the permutation is length n
permutation_list.append(permutation[:]) #store the completed
permutation
permutation.pop(-1) # knock off the last value and go to the next
element in "list"
return permutation_list


if __name__=='__main__':
list=['red','white','blue','green']
print permute(list,3)

 

[Miki Tebeka]

Hello Steve,

I am trying to come up with a way to develop all n-length permutations of a
given list of values.
###START CODE###
...

Side note:
Please make sure that when posting to a newgroup your lines are less than
78 charcters long.

I'd split the problem (If I understand it correctly) to two problems:
1. Find all sublist of size n of l
2. Find all permutations of a list l

And using generators is always fun

Something in the lines of:
#!/usr/bin/env python

def sublists(l, n):
'''All sublists in length 'n' of 'l' '''
assert(len(l) >= n)

if len(l) == n: # Recursion base
yield l
return

for i in range(len(l)): # Remove one item and recurse
for sub in sublists(l[:i] + l[i+1:], n):
yield sub

def permutations(l):
'''All permuatations of 'l' '''
if len(l) == 1: # Rercursion base
yield l
return

for i, v in enumerate(l):
for p in permutations(l[:i] + l[i+1:]):
yield [v] + p

def subperm(l, n):
'''All permutation of sublists in size 'n' of 'l' '''
for s in sublists(l, n):
for p in permutations(s):
yield p

if __name__ == "__main__":
from sys import argv

l = range(int(argv[1]))
n = int(argv[2])

for p in subperm(l, n):
print p

HTH.

 

[Jack Diederich]

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.

###START CODE###

[snip]

Combinatorics (permutations, combinations, etc) get golfed (shortest/fastest)
on c.l.py a couple times a year. Check groups.google.com for some solutions.
If you want fast, try probstat.sf.net which does some combinatorics in C with
a python wrapper. disclosure: I wrote it.

-Jack

 

[Alex Martelli]

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

 

[Steve Goldman]

Thanks to everyone for lots to think about. I really like the concept of
counting in base "X" as a model for this problem.

But now I have another question. In the elegant recursive generator, below,
the yield expression for the terminating condition is followed by a return
statement. Why is that necessary? I know it is, because I tried taking it
out with unhappy consequences. I thought yield had the same effect as
return, except that the function's state was "frozen" until the next
iteration.

Thanks again.

 

[Steven Bethard]

But now I have another question. In the elegant recursive generator, below,
the yield expression for the terminating condition is followed by a return
statement. Why is that necessary? [snip]

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

The 'return' statement tells the generator to exit the function (without
saving the state. So,
.... yield 1
.... return
.... yield 2
.... [1]

Note that the second yield is never reached. So the source of your example
above chose to use the 'return' statement instead of the perhaps more
intuitive (but slightly more indented):

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

Steve

 

[Alex Martelli]

Thanks to everyone for lots to think about. I really like the concept of
counting in base "X" as a model for this problem.

You're welcome.

But now I have another question. In the elegant recursive generator, below,
the yield expression for the terminating condition is followed by a return
statement. Why is that necessary? I know it is, because I tried taking it

It's not; a
raise StopIteration
or putting the rest of the program in an 'else:' would be just as good.

out with unhappy consequences. I thought yield had the same effect as
return, except that the function's state was "frozen" until the next
iteration.

You need to terminate the recursion sooner or later. To do that, you
must get a StopIteration exception raised. That happens with the
appropriate raise statement, or a return, or "falling off the end of the
code", which is equivalent to a return.

I generally prefer return, as it's concise and avoids extra nesting.
But if you'd rather do if/else, you can code, for example:

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

If you do choose an if/else it seems to me things are more readable when
you arrange them this way (rather than with if N<=0, so the for in the
else). Matter of tastes, of course.


Alex

 

[Hung Jung Lu]

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

If you do choose an if/else it seems to me things are more readable when
you arrange them this way (rather than with if N<=0, so the for in the
else). Matter of tastes, of course.

For an unreadable voodoo version, here is a one-liner:

permute = lambda Xs, N: reduce(lambda r, a: [p + [x] for p in r for x
in Xs], range(N), [[]])

print permute(['red', 'white', 'blue', 'green'], 3)

Actually, we should probably not call it "permute". In combinatorics,
"permutation" usually is reserved for sorting operation on a given
combination. However, I don't have a good name for the described
operation, either. Some people would probably call it "sequential draw
with replacement". It's more like "combination" as in the case of a
"combination lock", or as in "slot-machine combinations". (46 entries
in Google. Zero entry for "slot-machine permutations", quoted search
used.)

For simple permutation on a given list, the voodoo version is:

permutations = lambda x: reduce(lambda r, a: [p[:i] + [a] + p[i:] for
p in r for i in range(len(p)+1)], x[1:], [x[:1]])

print permutations(['a', 'b', 'c'])

No if/else statements. No explicit recursion. And it works for
zero-length lists as well. Now, if someone could do the general P(n,
k) and C(n, k) versions, I'd appreciate it.

Hung Jung

 

[Thorsten Kampe]

* Steve Goldman (2004-10-19 02:34 +0200)

I am trying to come up with a way to develop all n-length permutations of a
given list of values.

I'm sorry but there are no "n-length permutations" in
mathematics/combinatorics. There are variations and combinations -
each of them with and without repetition. The difference is that with
combinations order of the elements is irrelevant and with variations
order is relevant.

Permutations always have the full length of the original list.
Permutations are divided in permutations with and without repetition
(like combinations and variations).

For an (unoptimized) version of permutations see:
http://www.python.org/doc/current/ref/indentation.html


Thorsten

PS If you are interested I can post the code for all six
possibilities. The code computes optionally the size of the result
list (because this grows big very soon) so you don't run out of memory
or time

 

[Thorsten Kampe]

* Hung Jung Lu (2004-10-22 07:09 +0200)

Actually, we should probably not call it "permute". In combinatorics,
"permutation" usually is reserved for sorting operation on a given
combination.

Not at all. Permutations and combinations have nothing in common. And
permutations aren't "sorted".

 

[Hung Jung Lu]

No if/else statements. No explicit recursion. And it works for
zero-length lists as well. Now, if someone could do the general P(n,
k) and C(n, k) versions, I'd appreciate it.

Well, here they are: (for functional people, basically I used
tail-call and parameter list to emulate looping variables... standard
trick, nothing new. The formulas might be further simplified?)

permutations = lambda Xs, k: [p[0] for p in reduce(lambda r, i:
[[x+[y], y[:i]+y[i+1:]] for (x, y) in r for i in range(len(y))],
range(k), [[[], Xs]])]

combinations = lambda Xs, k: [p[0] for p in reduce(lambda r, i:
[[x+[y], y[i+1:]] for (x, y) in r for i in range(len(y))],
range(k), [[[], Xs]])]

slot_machine_combinations = lambda Xs, k: [p[0] for p in reduce(lambda
r, i: [[x+[y], y] for (x, y) in r for i in range(len(y))],
range(k), [[[], Xs]])]

sample = ['a', 'b', 'c', 'd']
print permutations(sample, 2)
print combinations(sample, 2)
print slot_machine_combinations(sample, 2)

The three formulas only differ in the treatment of the y[] lists in
looping. That part can be parametrized into separate lambdas if so
desired.

permutations: y --> y[:i] + y[i+1:]
combinations: y --> y[i+1:]
slot_machine_combinations: y --> y

Hung Jung