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)

### Tags

• (none)
▶ Show machine tags (5)

### Required Modules

• (none specified)