public

  • Download Gist
non_sequential_combinations.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
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:])

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.