Instantly share code, notes, and snippets.

# BlckKnght/non_sequential_combinations.py Created Mar 15, 2013

 from collections import deque from itertools import combinations try: from itertools import ifilter except ImportError: ifilter = filter # python 3 import timeit def abarnert(n, r): def good(combo): return not any(combo[i]+1 == combo[i+1] for i in range(len(combo)-1)) return ifilter(good, combinations(range(1, n+1), r)) def thkang_helper(rnge, r, prev=[]): if r == 0: yield prev else: for i, item in enumerate(rnge): for next_comb in thkang_helper(rnge[i+2:], r-1, prev+[item]): yield next_comb def thkang(n, r): return thkang_helper(list(range(1, n+1)), r) def svckr(n, r): # first combination, startng at 1, step-size 2 combination = list(range(1, r*2, 2)) # as long as all items are less than or equal to n while combination[r-1] <= n: yield tuple(combination) p = r-1 # pointer to the element we will increment a = 1 # number that will be added to the last element # find the rightmost element we can increment without # making the last element bigger than n while p > 0 and combination[p] + a > n: p -= 1 a += 2 # increment the item and # fill the tail of the list with increments of two combination[p:] = range(combination[p]+1, combination[p] + 2*(r-p), 2) def BlckKnght(n, r): if r == 0: yield () return for v in range(2*r-1, n+1): for c in BlckKnght(v-2, r-1): yield c + (v,) def Knoothe(n, r): for c in combinations(range(1, n-r+2), r): yield tuple(v+i for i, v in enumerate(c)) def JFSebastian_helper(seq, r): stack = [(0, r, ())] while stack: j, r, prev = stack.pop() if r == 0: yield prev else: for i in range(len(seq)-1, j-1, -1): stack.append((i+2, r-1, prev + (seq[i],))) def JFSebastian(n, r): return JFSebastian_helper(list(range(1, n+1)), r) def consume(f, *args, **kwargs): deque(f(*args, **kwargs)) def test(n, r, funcs): times = [timeit.timeit(lambda : consume(f, n, r), number=10) for f in funcs] count = len(list(BlckKnght(n, r))) template = "({:2d},{:2d}){:7d}" + " |{:8.4f}"*len(times) print(template.format(n, r, count, *times)) def do_tests(ns, rs, funcs=funcs, swap_nr=False): print("( n, r) #" + "".join(" |{:>8s}".format(f.__name__) for f in funcs)) for n in ns: print("==============" + "=+========"*len(funcs)) for r in rs: if swap_nr: test(r, n, funcs) else: test(n, r, funcs) funcs = (abarnert, thkang, svckr, BlckKnght, Knoothe, JFSebastian) if __name__ == "__main__": do_tests((16, 24), (2,4,6,8), funcs) do_tests((32,), (2,4,6,8), funcs[1:])