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 ago  # | flag

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)
Python recipes (4591)
Guang Shen Huang's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks