This recipe shows a way to solve the K-combinations problem without replacement with a sequence of items using the dynamic programming technique.
If you want a divine but slower solution take into account a "divide et impera" paradigm like in this recipe: http://code.activestate.com/recipes/190465-generator-for-permutations-combinations-selections/
This implementation could be improved overcoming some drawbacks. In particular, the inefficiency is due to the data structure used to store every set of combinations.
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
#!/usr/bin/env python __version__ = "0.8" """combinations.py This recipe shows a way to solve the K-combinations problem without replacement with a sequence of items using the dynamic programming technique. Keywords: combination, binomial coefficient 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 combinations(s, K): """ On entry: s sequence of items; K size of the combinations Returns: list of all possible 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+1) ] for n in range(1,N+1): newS = [ for i in range(K+1) ] for k in range(max(1, n-(N-K)), min(K+1, n+1)): 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 return S[K] if __name__ == '__main__': s = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] print combinations(s, 5)
Given s a sequence of items with size N and K the dimension of the combinations, it builds a (N+1,K+1) matrix S where each S(n,k) is calculated as follows:
S(n, k) = empty set n=0 or k=0 S(n, k) = S(n-1, k) + [comb+s(n-1) for comb in S(n-1, k-1)] n=1...N+1 and k=1...K+1
If the sequence is empty (n=0) or k=0, the solutions also will be empty.
In the general case (n,k) part of the solution is already computed by means of (n-1, k) while the remained combinations are in (n-1, k-1) adding the new element s(n-1) for each combination.
Indeed, there are some optimizations in the algorithm because to compute the n-th row we need only the (n-1)-th row for each iteration, so we just need two vectors (S and newS) to solve the problem. Furthermore, only some of the sub-problems needs to be resolved to get the final result in S[K] (this explain the range of the variable k)