Skip to content
Create a gist now

Instantly share code, notes, and snippets.

from collections import deque
from itertools import combinations
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
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 ()
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
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)
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:])
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.