Recursive function to develop permutations
Miki Tebeka
miki.tebeka at zoran.com
Tue Oct 19 11:19:14 CEST 2004
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.
--
------------------------------------------------------------------------
Miki Tebeka <miki.tebeka at gmail.com>
http://tebeka.spymac.net
The only difference between children and adults is the price of the toys
More information about the Python-list
mailing list