permIter() takes a sequence and returns an iterator that goes through all possible permutations of that sequence.
Python, 15 lines
Download
Copy to clipboard1 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 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.
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.