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

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.

Tags: algorithms

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

It also only seems to handle string sequence types.

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

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.