Welcome, guest | Sign In | My Account | Store | Cart

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

Python, 15 lines
 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

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.

2 comments

Carl Bray 21 years, 10 months ago  # | flag

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.

Doug Zongker 21 years, 8 months ago  # | flag

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.

Created by Danny Yoo on Sat, 5 Jan 2002 (PSF)
Python recipes (4591)
Danny Yoo's recipes (9)

Required Modules

  • (none specified)

Other Information and Tasks