def k_subsets_i(n, k): ''' Yield each subset of size k from the set of intergers 0 .. n - 1 n -- an integer > 0 k -- an integer > 0 ''' # Validate args if n < 0: raise ValueError('n must be > 0, got n=%d' % n) if k < 0: raise ValueError('k must be > 0, got k=%d' % k) # check base cases if k == 0 or n < k: yield set() elif n == k: yield set(range(n)) else: # Use recursive formula based on binomial coeffecients: # choose(n, k) = choose(n - 1, k - 1) + choose(n - 1, k) for s in k_subsets_i(n - 1, k - 1): s.add(n - 1) yield s for s in k_subsets_i(n - 1, k): yield s def k_subsets(s, k): ''' Yield all subsets of size k from set (or list) s s -- a set or list (any iterable will suffice) k -- an integer > 0 ''' s = list(s) n = len(s) for k_set in k_subsets_i(n, k): yield set([s[i] for i in k_set]) def __test__(): two_sets = list(k_subsets_i(10, 2)) assert len(two_sets) == 45 two_set = two_sets[0] assert len(two_set) == 2 class Tester: def __init__(self, i): self.i = i def __repr__(self): return 'Tester(%d)' % self.i super_set = [Tester(i) for i in range(100, 200, 10)] two_sets = list(k_subsets(super_set, 2)) assert len(two_sets) == 45 two_set = two_sets[0] assert len(two_set) == 2 assert isinstance(two_set.pop(), Tester) __test__() for two in k_subsets(range(20, 26), 2): print two # prints: set([24, 25]) set([25, 23]) set([25, 22]) set([25, 21]) set([25, 20]) set([24, 23]) set([24, 22]) set([24, 21]) set([24, 20]) set([22, 23]) set([21, 23]) set([20, 23]) set([21, 22]) set([20, 22]) set([20, 21])