ActiveState Code

Recipe 105962: Permutations using generators

permIter() takes a sequence and returns an iterator that goes through all possible permutations of that sequence.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def permIter(seq):
    """Given some sequence 'seq', returns an iterator that gives
    all permutations of that sequence."""
    ## Base case
    if len(seq) == 1:
        yield(seq[0])
        raise StopIteration

    ## Inductive case
    for i in range(len(seq)):
        element_slice = seq[i:i+1]
        rest_iter = permIter(seq[:i] + seq[i+1:])
        for rest in rest_iter:
            yield(element_slice + rest)
    raise StopIteration

Discussion

This implementation is nice because it allows one to traverse all the permutations of a sequence naturally, without incurring the cost of holding the whole thing in memory.

Comments

  1. 1. At 5:27 a.m. on 14 may 2002, Carl Bray said:

    Only handles strings. Will only work with Python 2.2 and you need to import generators

    from __future__ import generators

    It also only seems to handle string sequence types.

    I'll have a look at converting it to take lists.

  2. 2. At 12:04 p.m. on 14 jul 2002, Doug Zongker said:

    fix for general sequences. The base case should have "yield seq", not "yield seq[0]". This will make it work for all sequence types, not just strings.

Sign in to comment