http://stackoverflow.com/questions/15421886/generating-non-consecutive-combinations

combinations_benchmark.py

#!/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()