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.

Arnau Sanchez 15 years, 3 months ago

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 9 years, 2 months ago

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)

### Tags

▶ Show machine tags (4)

### Required Modules

• (none specified)