Welcome, guest | Sign In | My Account | Store | Cart

The usaual way to solve these problem is to inflate a huge list, thus it need a lot of memory. These two enumerator take a different approach. It use a linklist to imitate permutations, a binary tree to imitate combination. Thus the program can spit out the result one by one.

Python, 94 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94``` ```def CombinationEnumerator(listObj, selection) : class CombEnum(object) : def __init__(self, listObj, selection) : assert selection <= len(listObj) self.items = listObj self.route = ([True, ]*selection) + [False, ]*(len(listObj)-selection) self.selection = selection def value(self) : result = [ val for flag, val in zip(self.route, self.items) if flag ] return result def next(self) : try : while self.route[-1] : self.route.pop() while not self.route[-1] : self.route.pop() except : return False self.route[-1] = False count = self.route.count(True) self.route.extend( (self.selection - count) * [True,] ) padding = len(self.items) - len(self.route) self.route.extend( padding * [False, ]) return True if selection == 0 : yield [] return rotor = CombEnum(listObj, selection) yield rotor.value() while rotor.next() : yield rotor.value() def PermutationEnumerator(choice, selection = None) : if not selection : selection = len(choice) class Rotor(object) : def __init__(self, choice, selection, parent = None) : assert len(choice) >= selection self.selection = selection self.parent = parent self.choice = choice self.cursor = 0 if selection == 1 : self.child = None else : self._spawn_child() def value(self) : if self.child : result = self.child.value() result.append(self.choice[self.cursor]) return result else : return [ self.choice[self.cursor], ] def _spawn_child(self) : assert self.selection >= 2 cursor = self.cursor child_choice = self.choice[:cursor] + self.choice[cursor + 1:] self.child = Rotor(child_choice, self.selection -1, self) def next(self) : result = False if self.child : result = self.child.next() if result : return result else : self.cursor += 1 if self.cursor == len(self.choice) : return False else : if self.child : self._spawn_child() return True rotor = Rotor(choice, selection) yield rotor.value() while rotor.next() : yield rotor.value() if __name__ == "__main__" : items = [ 'a', 'b', 'c'] for algo in (CombinationEnumerator, PermutationEnumerator) : for selection in range(1, 4) : print algo.__name__ print items print selection enum = algo(items, selection) for i in enum : print i print "\n\n\n" ```

When we enumerate the permutation of a list by hand, we would first pick out an element and then select in the rest. Say the list is ['a', 'b', 'c'] and we pick out 'a', then we should permute 'b' and 'c'. However, when we finish with 'a' part and begin with 'b', the supplimentary list got changed. This is a typical linked list, and the new stuff is to dynamically and recursively construct it.

As to combination, every element has two state, either be selected or not. Thus it forms a binary tree. In my code, self.route is just a route to travel this tree. Every node stretches out two roads towards its child. In my code I use True and False to represent these two routes, within which True means to include and False means to exclude. All we want to do now, is just to enumerate all the routes that has given number of True.

next() is based on the following notion: the first route should begin with a streak of True and end with a streak of False; and the last route should begin with a streak of False and end with a streak of True. next() then identify the finished part of the existing tree, find its root, shift to another subtree.

Ironically when I begin to code, I find it is totally unnecessary to construct such a tree, a dry list of True and False is sufficient.

#### 1 comment

Raymond Hettinger 18 years, 1 month ago

Much simpler and clearer version.

``````def perm(items, n=None):
if n is None:
n = len(items)
for i in range(len(items)):
v = items[i:i+1]
if n == 1:
yield v
else:
rest = items[:i] + items[i+1:]
for p in perm(rest, n-1):
yield v + p

def comb(items, n=None):
if n is None:
n = len(items)
for i in range(len(items)):
v = items[i:i+1]
if n == 1:
yield v
else:
rest = items[i+1:]
for c in comb(rest, n-1):
yield v + c
``````
 Created by Guang Shen Huang on Tue, 7 Mar 2006 (PSF)

### Required Modules

• (none specified)