secret
Created

  • Download Gist
combinations_benchmark.py
Python
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
#!/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()

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.