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