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) 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.