1

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]
"""
1
Contributor
1
Reply
14
Views
11 Years
Discussion Span
Last Post by vegaseat
1

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
'''
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.