Instantly share code, notes, and snippets.

# zed/combinations_benchmark.pySecret Created Mar 15, 2013

 #!/usr/bin/env python import functools import itertools from collections import deque from copy import deepcopy try: range = xrange except NameError: range = range # Python 3 try: from itertools import ifilter as filter, imap as map except ImportError: filter = filter # Python 3 map = map # https://gist.github.com/zed/4276624#file-reporttime-py from reporttime import accept_funcs, get_functions_with_prefix, measure def _combinations_svckr(n, r): if r > n: return if n == 0 or r == 0: yield () return # 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 combinations_svckr(seq, r): assert seq == list(range(1, len(seq)+1)) return _combinations_svckr(len(seq), r) def _combinations_blckknght(r, n): if r == 0: yield () return for v in range(2*r-1, n+1): for c in _combinations_blckknght(r-1, v-2): yield c + (v,) def combinations_blckknght(seq, r): assert seq == list(range(1, len(seq)+1)) return _combinations_blckknght(r, len(seq)) def _combinations_knoothe(n, r): def y2x(y): """ y_1 = x_1 y_2 = x_2 - 1 y_3 = x_3 - 2 ... y_r = x_r - (r-1) """ return tuple(yy + i for i, yy in enumerate(y)) return map(y2x, itertools.combinations(range(1, n-r+1+1), r)) def combinations_knoothe(seq, r): assert seq == list(range(1, len(seq)+1)) return _combinations_knoothe(len(seq), r) def combinations_thkang(rnge, r, prev=[]): if r == 0: yield tuple(prev) else: for i, item in enumerate(rnge): for next_comb in combinations_thkang(rnge[i+2:], r-1, prev+[item]): yield next_comb def combinations_thkang_tuple(seq, r, prev=()): if r == 0: yield prev else: for i, item in enumerate(seq): for next_comb in combinations_thkang_tuple(seq[i+2:], r-1, prev+(item,)): yield next_comb if sys.version_info[:2] >= (3, 3): exec(""" def combinations_thkang_yield_from(seq, r, prev=()): if r == 0: yield prev else: for i, item in enumerate(seq): yield from combinations_thkang_yield_from(seq[i+2:], r-1, prev+(item,)) """) def combinations_stack(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 combinations_abarnert(p, r): def good(combo): return not any(combo[i]+1 == combo[i+1] for i in range(len(combo)-1)) return filter(good, itertools.combinations(p, r)) @accept_funcs def test_funcs(funcs, args): """Check that all functions produce the same result.""" orig_args = deepcopy(args) expected = sorted(funcs[0][1](*args)) for name, f in funcs: r = sorted(f(*args)) assert r == expected, (name, args, r, expected) assert orig_args == args, name def consume_returned(func): @functools.wraps(func) def wrapper(*args): deque(func(*args), maxlen=0) return wrapper def main(): funcs = get_functions_with_prefix('combinations_') for f in funcs[:]: try: print(list(f(list(range(1, 5)), 2))) except Exception as e: print("remove %s, error: %s" % (f.__name__, e)) funcs.remove(f) for n in range(8): for r in range(12): args = (list(range(1, n+1)), r) test_funcs(funcs, args) funcs = [consume_returned(f) for f in funcs] for n, r in [(8, 4), (16, 4), (32, 4), (32, 8)]: args = (list(range(1, n+1)), r) measure(funcs, args, comment="%s %s" % (n, r)) main()
to join this conversation on GitHub. Already have an account? Sign in to comment