これが私の再帰ジェネレーターです（アイテムが選択されているn+1場合、アイテムをスキップするだけnです）：
def non_consecutive_combinator(rnge, r, prev=[]):
if r == 0:
yield prev
else:
for i, item in enumerate(rnge):
for next_comb in non_consecutive_combinator(rnge[i+2:], r-1, prev+[item]):
yield next_comb
print list(non_consecutive_combinator([1,2,3,4], 2))
#[[1, 3], [1, 4], [2, 4]]
print list(non_consecutive_combinator([1,2,3,4,5], 2))
#[[1, 3], [1, 4], [1, 5], [2, 4], [2, 5], [3, 5]]
print list(non_consecutive_combinator(range(1, 10), 3))
#[[1, 3, 5], [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9], [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 8], [1, 6, 9], [1, 7, 9], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 8], [2, 6, 9], [2, 7, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 8], [3, 6, 9], [3, 7, 9], [4, 6, 8], [4, 6, 9], [4, 7, 9], [5, 7, 9]]
効率について:
このコードは、スタックをトラバースし、各反復で新しいコレクションを構築するため、O(1) にすることはできません。また、再帰ジェネレーターは、アイテムの組み合わせrを取得するために最大スタック深度を使用する必要があることを意味します。rこれは、 lowrを使用すると、スタックを呼び出すコストが非再帰生成よりも高くなる可能性があることを意味します。と が十分nにrあれば、 itertools ベースのソリューションよりもはるかに効率的である可能性があります。
私はこの質問で2つのアップロードされたコードをテストしました:
from itertools import ifilter, combinations
import timeit
def filtered_combi(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 non_consecutive_combinator(rnge, r, prev=[]):
if r == 0:
yield prev
else:
for i, item in enumerate(rnge):
for next_comb in non_consecutive_combinator(rnge[i+2:], r-1, prev+[item]):
yield next_comb
def wrapper(n, r):
return non_consecutive_combinator(range(1, n+1), r)
def consume(f, *args, **kwargs):
deque(f(*args, **kwargs))
t = timeit.timeit(lambda : consume(wrapper, 30, 4), number=100)
f = timeit.timeit(lambda : consume(filtered_combi, 30, 4), number=100)
結果とその他の結果（編集）（windows7、python 64bit 2.7.3、8GB RAMのコアi5アイビーブリッジ）：
(n, r) recursive itertools
----------------------------------------
(30, 4) 1.6728046 4.0149797 100 times 17550 combinations
(20, 4) 2.6734657 7.0835997 1000 times 2380 combinations
(10, 4) 0.1253318 0.3157737 1000 times 35 combinations
(4, 2) 0.0091073 0.0120918 1000 times 3 combinations
(20, 5) 0.6275073 2.4236898 100 times 4368 combinations
(20, 6) 1.0542227 6.1903468 100 times 5005 combinations
(20, 7) 1.3339530 12.4065561 100 times 3432 combinations
(20, 8) 1.4118724 19.9793801 100 times 1287 combinations
(20, 9) 1.4116702 26.1977839 100 times 220 combinations
ご覧のとおり、再帰的なソリューションと itertools.combination ベースのソリューションの間のギャップは、上になるほど大きくnなります。
実際、両方のソリューション間のギャップが大きく依存しているため、rより大きなrものは、から生成されたより多くの組み合わせを破棄する必要があることを意味しますitertools.combinations。例えば の場合n=20, r=9: 167960(20C9) の組み合わせの中から 220 の組み合わせのみをフィルタリングして取得します。nとrが小さい場合、 itertools.combinationsr が少ないほど効率的であり、説明したようにスタックを使用しないため、使用が高速になります。(ご覧のとおり、 itertools は非常に最適化されています ( 、 、および一連のジェネレーターとリストの内包表記でロジックを記述した場合、foritertoolsifでwhile抽象化されたものほど速くはなりません)。 python が大好き - コードをより高いレベルに引き上げると、報酬が得られます。そのための言語は多くありません。