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

Reorder a sequence (uses generators, and recursion!) (Python recipe) by Michael Davies
ActiveState Code (http://code.activestate.com/recipes/252178/)

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

Python, 8 lines
Download
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:]

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

Tags: search

2 comments

Arnau Sanchez 16 years, 9 months ago  # | flag

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.

Chris Laffra 10 years, 7 months ago  # | flag

If you swap the two for-loops, you get a sorted version that humans probably like better:

def all_perms(s):
    if len(s) <= 1: 
        yield s
    else:
        for i in range(len(s)):
            for p in permutations(s[:i] + s[i+1:]):
                yield s[i] + p

For input 'ABCD', this produces: 

'ABCD' 'ABDC' 'ACBD' 'ACDB' 'ADBC' 'ADCB' 'BACD' 'BADC' 'BCAD' 'BCDA' ...

rather than the more "random" looking:

'ABCD' 'BACD' 'BCAD' 'BCDA' 'ABDC' 'BADC' 'BDAC' 'BDCA' 'ACBD' 'CABD' ...
Created by Michael Davies on Fri, 28 Nov 2003 (PSF)
◄ Python recipes (4591) ►
◄ Michael Davies's recipes (1) ►

Required Modules

  • (none specified)

Other Information and Tasks