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

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

Python, 8 lines
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.

2 comments

Arnau Sanchez 14 years, 4 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 8 years, 2 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