まあ、私はまだこれを楽しんでいます;-)
これが中断したところで、最小化しようとしていることが明らかになりました。
sum(n*(n-1)//2 for n in index2count.values())
すべての値が同じ場合 (可能な場合)、または 2 つの異なる値が 1 つ離れている場合 (if のようにlen(full_set) = 10、7 つの 3 と 3 つの 4) は最小限です。計算をまったく行わないジェネレーターを作成するには、これで十分index2countです。代わりhiに、2 つの値のうち大きい方のインデックスのセットとlo、残りのインデックス (loすべての (概念的な! 計算されていない) 値が同じ場合は空です)。
Kこれは引数を削除し、重複に対して別のアプローチをとります: 重複を無視します。ここで重複を追跡するのはコストがかかり、不器用です。重複は、「ランダムっぽい」ジェネレーターで実際に予想されるはずです。それが気になる場合は、別のルーチンでラップして重複を取り除きます。
出力例:
>>> from itertools import islice
>>> for s in islice(gen_subsets_special(set(range(5)), 1), 10):
... print s
set([4])
set([3])
set([0])
set([1])
set([2])
set([0])
set([3])
set([1])
set([2])
set([4])
>>> for s in islice(gen_subsets_special(set(range(10, 20)), 3), 10):
... print s
set([17, 18, 10])
set([11, 12, 14])
set([16, 19, 13])
set([12, 13, 15])
set([17, 10, 11])
set([16, 19, 15])
set([17, 18, 14])
set([16, 18, 13])
set([19, 12, 15])
set([10, 11, 14])
コードは次のとおりです。
def gen_subsets_special(full_set, M, seed=123456):
# generate randomish M-subsets of full_set, "far apart".
import random
from random import sample
random.seed(seed)
elements = list(full_set)
N = len(elements)
hi = set(range(N))
lo = set()
while True:
assert not (hi & lo)
assert len(lo | hi) == N
# First take indices from hi, then (if needed) from lo.
if len(hi) > M:
# We can take all of them from hi, with some left over.
ixhi = set(sample(hi, M))
ixlo = set()
# The ixhi counts go down by 1, so move 'em to lo
hi -= ixhi
lo |= ixhi
assert hi
else:
# We need to take everything in hi.
ixhi = hi.copy()
ixlo = set(sample(lo, M - len(ixhi)))
hi |= lo - ixlo
lo = ixlo
assert not (ixlo & ixhi)
ix = ixlo | ixhi
assert len(ix) == M
yield set(elements[i] for i in ix)
構築により、生成されたシーケンスのすべてのプレフィックスは、プレフィックス内のセットのすべてのペアの交差のサイズの合計を最小化します。または、今の私にはそう思われます;-)
最後に、より明らかに、すべてのインデックスを繰り返し循環するバリエーションです。これはおそらく私が実際に使用するものです：
def gen_subsets_special(full_set, M, seed=123456):
# generate randomish M-subsets of full_set, "far apart".
import random
from random import sample
random.seed(seed)
elements = list(full_set)
allix = set(range(len(elements)))
takefrom = allix.copy()
def destructive_sample(n):
# Remove a random n-subset from takefrom, & return it.
s = set(sample(takefrom, n))
takefrom.difference_update(s)
return s
while True:
if len(takefrom) >= M:
# Get everything from takefrom.
ix = destructive_sample(M)
else:
# We need to take all of takefrom, and more.
ix = takefrom
takefrom = allix - ix
ix |= destructive_sample(M - len(ix))
assert len(ix) == M
yield set(elements[i] for i in ix)