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

From the previous recipe http://code.activestate.com/recipes/577764-combinations-of-a-sequence-without-replacement-usi/ we can easily build a generator that return all the K-combinations without replacement.

Python, 52 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
#!/usr/bin/env python

__version__ = "0.8"

"""xcombinations.py

This recipe shows a way to solve the K-combination problems without replacement
of a N items sequence using the dynamic programming technique.

Keywords: combination, binomial coefficient, generator

See also: http://code.activestate.com/recipes/577764-combinations-of-a-sequence-without-replacement-usi/
See also: http://code.activestate.com/recipes/190465-generator-for-permutations-combinations-selections/ 
See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/105962
See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66463
See also: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66465

"""



def xcombinations(s, K):
    """
    On entry: s sequence of items; K size of the combinations
    Returns: generator of the K-combinations without replacement of
    s.
    """
    N = len(s)
    assert K<=N, 'Error K must be less or igual than N'
    S = [[] for i in range(K) ]
    for n in range(1,N+1):
        newS = [[] for i in range(K) ]
        for k in range(max(1, n-(N-K)), min(K+1, n+1)):
            if k == K:
                for el in S[k-1]:
                    yield el+[s[n-1]] 
            else:
                newS[k].extend(S[k])
                if len(S[k-1])==0:
                    newS[k].append([s[n-1]])
                else:
                    newS[k].extend( [el+[s[n-1]] for el in S[k-1]] )
        S = newS



if __name__ == '__main__':

    s = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

    for c in xcombinations(s, 5):
        print c

For each S(n, K) where n=0...N appears the partial solutions of S(N, K). So, it returns a combination every time it's available. Now the vector S and newS, representing the matrix solutions, are no longer with size K because they doesn't need to store all the combinations up to the final execution of the function.

Created by Filippo Squillace on Tue, 21 Jun 2011 (MIT)
Python recipes (4591)
Filippo Squillace's recipes (12)

Required Modules

  • (none specified)

Other Information and Tasks