Skip to content
Create a gist now

Instantly share code, notes, and snippets.

Embed URL


Subversion checkout URL

You can clone with
Download ZIP
#!/usr/bin/env python
import functools
import itertools
from collections import deque
from copy import deepcopy
range = xrange
except NameError:
range = range # Python 3
from itertools import ifilter as filter, imap as map
except ImportError:
filter = filter # Python 3
map = map
from reporttime import accept_funcs, get_functions_with_prefix, measure
def _combinations_svckr(n, r):
if r > n:
if n == 0 or r == 0:
yield ()
# 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 ()
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)
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
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):
def combinations_thkang_yield_from(seq, r, prev=()):
if r == 0:
yield prev
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
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))
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):
def wrapper(*args):
deque(func(*args), maxlen=0)
return wrapper
def main():
funcs = get_functions_with_prefix('combinations_')
for f in funcs[:]:
print(list(f(list(range(1, 5)), 2)))
except Exception as e:
print("remove %s, error: %s" % (f.__name__, e))
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.