A Simple Recursive Permutation Function (Python)

vegaseat 1 6K Views

A permutation is the arrangement of a set of items in different order. One interesting application is the rearrangement of characters in a word to create other words. If all the n characters are unique, you should get n! unique permutations. You can make a list of words unique by converting it to a set.

# a simple recursive permutation function
# the number of permutations of a sequence of n unique items is given by n! (n factorial)
# more details at http://mathworld.wolfram.com/Permutation.html
# tested with Python24      vegaseat      16feb2006

def permutate(seq):
    """permutate a sequence and return a list of the permutations"""
    if not seq:
        return [seq]  # is an empty sequence
    else:
        temp = []
        for k in range(len(seq)):
            part = seq[:k] + seq[k+1:]
            #print k, part  # test
            for m in permutate(part):
                temp.append(seq[k:k+1] + m)
                #print m, seq[k:k+1], temp  # test
        return temp

# test the module
if __name__ == "__main__":
    # permutate a string, how many recognizable words does this generate?
    print permutate('owl')
    print permutate('art')
    # test for duplicates
    blist = permutate('bush')
    print "items in bush list =", len(blist)      # should be 4! or 1*2*3*4 = 24
    print "items in bush set  =", len(set(blist)) # should be the same
    tlist = permutate('tart')
    print "items in tart list =", len(tlist)      # should be 4! or 1*2*3*4 = 24
    print "items in tart set  =", len(set(tlist)) # less unique since there are two 't'
    # permutate a list
    list1 = [7, 8, 9]
    for list2 in permutate(list1):
        print list2

"""
result =
['owl', 'olw', 'wol', 'wlo', 'low', 'lwo']
['art', 'atr', 'rat', 'rta', 'tar', 'tra']
items in bush list = 24
items in bush set  = 24
items in tart list = 24
items in tart set  = 12
[7, 8, 9]
[7, 9, 8]
[8, 7, 9]
[8, 9, 7]
[9, 7, 8]
[9, 8, 7]
"""
Member Avatar for vegaseat
vegaseat 1,735 DaniWeb's Hypocrite

Starting with Python version 2.6 a permutate function has been added in the module itertools in the form of a generator itertools.permutations(iterable, r=None) ...

''' itertools_permutations.py
itertools.permutations(iterable, r=None) is a generator

If r is not specified or is None, then r defaults to the length of
the iterable and all possible full-length permutations are generated
'''

# needs Python26 or higher
from itertools import permutations

for p in permutations('art'):
    # join tuple p to a string
    print("".join(p))

''' result ...
art
atr
rat
rta
tar
tra
'''
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview