*n*items. Why? We don't know. But we do know how to do it: seed with a list containing a single list containing a single item:

`[['a']]`

. Then step through each of the lists in our list, and make copies, inserting the next item ('b') at each index, so we get `[['b', 'a'], ['a', 'b']]`

. Then we take this list as our seed and go round again, inserting the next item ('c'), so we get `[['c', 'b', 'a'], ['b', 'c', 'a'], ['b', 'a', 'c'], ['c', 'a', 'b'], ['a', 'c', 'b'], ['a', 'b', 'c']]`

. And so on and so on, until we've permuted all of our items. These lists get pretty big pretty quickly (the length of the list is n! so 10 items generates 3628800 combinations, and doing this may bring your computer to its knees).I first tackled this problem ~10 years ago, but I don't think my solution then was as elegant as this one.

#!/usr/bin/env python

import sys

# class representing a list of permutations

class Unit(list):

# count the total number of Units spawned

count = 0

def __init__(self, seed = None):

# if this is the first Unit created, we need to prepare the seed

if Unit.count == 0: seed = [[seed]]

Unit.count += 1

# call our superclass. We are just a fancy list

super(Unit, self).__init__(seed)

# produce a new generation, splicing in the passed in value

def spawn(self, interloper):

# a temporary working list

l = []

# for each of our existing lists

for u in self:

# for each index (including length + 1)

for i in range(0, len(u) + 1):

# take a copy of the list

a = Unit(u)

# insert the new value at this index

a.insert(i, interloper)

# and add the modified copy to our working list

l.append(a)

# when we're done, return a new Unit seeded with the list we just built

return Unit(l)

# calculate and show some stats

def stats(self):

self.items = len(self[0])

self.combinations = len(self)

return "%d items, %d permutations" % (self.items, self.combinations)

# simple wrapper class representing the set of items we want to permute

class Inventory(list):

def __init__(self, chars):

# we are yet another variation on a list

super(Inventory, self).__init__(chars)

# do we have more items to give?

def has_next(self):

return len(self) > 0

# shift the first item off of the list

def next(self):

return self.pop(0)

# wrapper class that actually does the work. We extend the Unit class mainly

# because we want its stats() method

class Permutations(Unit):

def __init__(self, items):

# we need an inventory

self.i = Inventory(items)

# get the first item off of the inventory

self.u = Unit(self.i.next())

# now while the inventory has more items to give us

while self.i.has_next():

# make another generation of Units fed with the next item

self.u = self.u.spawn(self.i.next())

# at the end, we become whatever the final Unit.spawn() gave us

self.extend(self.u)

# if we're called on the command line

if __name__ == '__main__':

# we will permute the command line arguments

permutables = sys.argv[1:]

# if we got no arguments, default to this

if not permutables:

permutables = ["life", "the universe", "everything"]

# do the work

p = Permutations(permutables)

# sort the result (a Permutation is just a fancy list, after all)

p.sort()

# and print it

print p

print p.stats()

Get the code here:

`svn co http://pikesley.homedns.org/svn/code/Combinatrics/tags/Release-2.0`

## No comments:

## Post a Comment