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.
Download
Copy to clipboard1 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.
Much simpler and clearer version.