ActiveState Powered by ActiveState

Recipe 252178: Reorder a sequence (uses generators, and recursion!)

Small function to generate every permutation of a given sequence. Works for lists and strings

Python 
1
2
3
4
5
6
7
8
def all_perms(str):
    if len(str) <=1:
        yield str
    else:
        for perm in all_perms(str[1:]):
            for i in range(len(perm)+1):
                #nb str[0:1] works in both string and list contexts
                yield perm[:i] + str[0:1] + perm[i:]

Discussion

This approach allows you to examine every permutation of a given sequence without sucking up too much memory.

Comments

  1. 1. At 6:18 a.m. on 5 aug 2007, Arnau Sanchez said:

    Slightly different version.

    def permutations(lst):
    remove = lambda lst0, index: lst0[:index] + lst0[index+1:]
    if lst:
        for index, x in enumerate(lst):
            for y in permutations(remove(lst, index)):
                yield (x,)+y
    else: yield ()

    Although it does not work the same way with strings.

Sign in to comment