# Naive Python program to print all combinations of k of n items. # Runs in time O(2^n), regardless of k (this is terrible). # Uses bignums to represent subsets of {1, 2, ..., n}: # bit i (starting with 1 for the least significant bit) indicates # that i is in the set. # By running through all numbers from 1 to 2^n-1, we can consider all # possible subsets. import sys def bits(k): # how many bits are set in k? rtn = 0 while k != 0: if k % 2 == 1: rtn += 1 k //= 2 return rtn def stringify(k): # return the subset represented by k s = "" v = 1 while k != 0: if k % 2 == 1: s += " " + str(v) k //= 2 v += 1 return s # This is an iterator. It /yield/s all appropriate values, one at a time, # in a way that allows us to drive a /for/ loop. # def combinations(k, n): for i in range(0, 2**n): if bits(i) == k: yield stringify(i) if len(sys.argv) != 3: sys.stderr.write("usage: %s k n\n" % sys.argv[0]) sys.exit(1) for s in combinations(int(sys.argv[1]), int(sys.argv[2])): print(s)