Pattern for permutations?

[Carl Banks]

Tim Churches wrote:
> This may be an elementary question but the solution is
> not obvious to me.

When you start doing stuff to lists in a general and arbitrarily deep
way, recursion is your friend.  Learn to think recursively first, then
iteratively second.


> I want to define a function which takes as its argument a
> list which contains one or more sequences, and then does stuff
> with every permutation of the elements of those sequences. For
> example, a function which works for a list containing three
> sequences:
> 
> def nestedloops(list_of_sequences):
>        for element0 in list_of_sequences[0]:
>                for element1 in list_of_sequences[1]:
>                        for element2 in list_of_sequences[2]:
>                                # do stuff with each permutation
>                                print element0, element1, element2
> 
> nestedloops([(1,2,3),('one','two','three'),('isa','dalawa','tatlo')])
> 
> How does one generalise such a function so that it handles any number 
> of sequences in the passed list of sequences i.e. a dynamic number of
> levels of nesting? 

Here's the basic idea:

Write a function that accepts a stub list, and a list of sequences
that you want to permute.  Suppose your function takes the following
arguments:

stub=[], seqs=[(1,2,3),('one','two','three')]

What it should do is recursively call itself once for each element of
seqs[0].  It should call itself with that element added to the end of
the stub list, and the first subsequence removed from seqs.  Thus,
your function should make these three calls:

stub=[1], seqs=[('one','two','three')]
stub=[2], seqs=[('one','two','three')]
stub=[3], seqs=[('one','two','three')]

When called with these arguments, the function, since it is the same
function, will do the same thing: call itself for each element of
seqs[0], with the element added to stub, and the seqs[0] removed.
When called, the function would have the arguments (for the first case
above):

stub=[1,'one'], seqs=[]
stub=[1,'two'], seqs=[]
stub=[1,'three'], seqs=[]

In this case, seqs is an empty list.  That is the signal that the stub
list contains the entire permutation.  So the function must test
whether seqs is empty, and if it is, do the desired operation.

This technique is a cliche of functional programming, and it is very
useful when you have arbitrarily nested stuff.


Here is the code:

    def permute_op (op, seqs):
        "Apply function op to each permutation of the sequences in seqs."
        _sub_permute_op (op, [], seqs)

    def _sub_permute_op (op, stub, seqs):
        if seqs:
            for p in seqs[0]:
                _sub_permute_op (op, stub+[p], seqs[1:])
        else:
            op (cseq)


You can do this iteratively, however.  The iterative method might be
easier on the computer but is harder on the programmer.

    import operator

    def permute_op (op, seqs):
        "Apply function op to each permutation of the sequences in seqs."

        nseqs = len(seqs)
        seqrange = range(0,nseqs)
        perm = [None]*nseqs
        lengths = map(len,seqs)
        nperms = reduce(operator.mul,lengths)

        for i in xrange(0,nperms):
            for j in seqrange:
                perm[j] = seqs[j][i%lengths[j]]
                i = i / lengths[j]
                #### Careful--the above won't work as of Python 3.0 ####
            op (perm)


> It occurred to me that the function could emit dynamic code for the 
> "for" loops and then eval() that, but that seems a bit messy and
> possibly slow.
> 
> Is there a better way?

Unless you're programming in LISP, there's always a better way than
self-modifying code.


-- 
CARL BANKS                                http://www.aerojockey.com
"Nullum mihi placet tamquam provocatio magna.  Hoc ex eis non est."