ASPN : Python Cookbook : Reorder a sequence (uses generators, and recursion!)

Title: Reorder a sequence (uses generators, and recursion!)
Submitter: Michael Davies (other recipes)
Last Updated: 2003/11/28
Version no: 1.0
Category: Searching

5 stars 1 vote(s)

Description:

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

Source: Text Source

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.

Add comment

Number of comments: 1

Slightly different version, Arnau Sanchez, 2007/08/05
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.
Add comment

Highest rated recipes:

1. A simple XML-RPC server

2. Web service accessible ...

3. Wrapping template engine ...

4. Assignment in expression

5. SOLVING THE METACLASS ...

6. Povray for python

7. Calling Windows API ...

8. Generic filter logic ...

9. Function Decorators by ...

10. MS SQL Server log monitor