一度に6つの値を選択することにより、データセットの3つの値の組み合わせすべてを効率的に生成するアルゴリズムを探しています。
データセットのすべての可能な3タプルの組み合わせを累積的に表現する6タプルの小さなセットを効率的に生成するアルゴリズムを探しています。
たとえば、可能な3枚のカードのすべての組み合わせを表す6枚のカードのトランプの手を計算します。
たとえば、データセットが与えられた場合：
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
6つの値の最初の「選択」は次のようになります。
['a','b','c','d','e','f']
そして、これは3つの値の組み合わせをカバーしています。
('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'b', 'e'), ('a', 'b', 'f'), ('a', 'c', 'd'),
('a', 'c', 'e'), ('a', 'c', 'f'), ('a', 'd', 'e'), ('a', 'd', 'f'), ('a', 'e', 'f'),
('b', 'c', 'd'), ('b', 'c', 'e'), ('b', 'c', 'f'), ('b', 'd', 'e'), ('b', 'd', 'f'),
('b', 'e', 'f'), ('c', 'd', 'e'), ('c', 'd', 'f'), ('c', 'e', 'f'), ('d', 'e', 'f')
それは明らかに次の方法で可能です。
- すべてのトリプレットの組み合わせを計算する
- 6つの値を選択
- これらの6つの値のすべてのトリプレットの組み合わせを計算する
- これらの組み合わせを最初の計算から削除する
- すべてが説明されるまで繰り返す
この例では、2600の可能なトリプレットの組み合わせが(26*25*24)/(3*2*1) == 2600あり、上記の「強引な」方法を使用すると、すべてのトリプレットの組み合わせを約301の6値グループで表すことができます。
しかし、これを達成するためのより効率的な方法があるはずだと感じています。
私の好みの言語はですがpython、これをで実装することを計画していC++ます。
アップデート
これが「ブルートフォース」するための私のPythonコードです。
from itertools import combinations
data_set = list('abcdefghijklmnopqrstuvwxyz')
def calculate(data_set):
all_triplets = list(frozenset(x) for x in itertools.combinations(data_set,3))
data = set(all_triplets)
sextuples = []
while data:
sxt = set()
for item in data:
nxt = sxt | item
if len(nxt) > 6:
continue
sxt = nxt
if len(nxt) == 6:
break
sextuples.append(list(sxt))
covers = set(frozenset(x) for x in combinations(list(sxt),3))
data = data - covers
print "%r\t%s" % (list(sxt),len(data))
print "Completed %s triplets in %s sextuples" % (len(all_triplets),len(sextuples),)
calculate(data_set)
301六重奏で2600トリプレットを完了
これよりも計算効率の良いものを探しています。
アップデート
Senderleは、興味深いソリューションを提供しました。データセットをペアに分割してから、ペアの可能なすべてのトリプレットを生成します。これは私が思いついたものよりも間違いなく優れています。
すべてのトリプレットがカバーされているかどうかを確認し、トリプレットカバレッジの冗長性を評価するための簡単な機能は次のとおりです。
from itertools import combinations
def check_coverage(data_set,sextuplets):
all_triplets = dict.fromkeys(combinations(data_set,3),0)
sxt_count = 0
for sxt in sextuplets:
sxt_count += 1
for triplet in combinations(sxt,3):
all_triplets[triplet] += 1
total = len(all_triplets)
biggest_overlap = overlap = nohits = onehits = morehits = 0
for k,v in all_triplets.iteritems():
if v == 0:
nohits += 1
elif v == 1:
onehits += 1
else:
morehits += 1
overlap += v - 1
if v > biggest_overlap:
biggest_overlap = v
print "All Triplets in dataset: %6d" % (total,)
print "Total triplets from sxt: %6d" % (total + overlap,)
print "Number of sextuples: %6d\n" % (sxt_count,)
print "Missed %6d of %6d: %6.1f%%" % (nohits,total,100.0*nohits/total)
print "HitOnce %6d of %6d: %6.1f%%" % (onehits,total,100.0*onehits/total)
print "HitMore %6d of %6d: %6.1f%%" % (morehits,total,100.0*morehits/total)
print "Overlap %6d of %6d: %6.1f%%" % (overlap,total,100.0*overlap/total)
print "Biggest Overlap: %3d" % (biggest_overlap,)
Senderleのsextupletsジェネレーターを使用して、繰り返されるトリプレットがローカライズされ、データセットのサイズが大きくなるにつれて、リピートが比例してよりローカライズされ、ピークリピートが大きくなることを観察することに魅了されています。
>>> check_coverage（range（26）、sextuplets（range（26））） データセット内のすべてのトリプレット：2600 sxtからのトリプレットの合計：5720 6人組の数：286 2600の0を逃した：0.0％ 2600のHitOnce2288：88.0％ 2600のHitMore312：12.0％ 2600のオーバーラップ3120：120.0％ 最大のオーバーラップ：11 >>> check_coverage（range（40）、sextuplets（range（40））） データセット内のすべてのトリプレット：9880 sxtからのトリプレットの合計：22800 6人組の数：1140 9880の0を逃した：0.0％ 9880のHitOnce9120：92.3％ 9880のHitMore760：7.7％ 9880の重複12920：130.8％ 最大のオーバーラップ：18 >>> check_coverage（range（80）、sextuplets（range（80））） データセット内のすべてのトリプレット：82160 sxtからのトリプレットの合計：197600 6人組の数：9880 82160の0を逃した：0.0％ 82160のHitOnce79040：96.2％ 82160のHitMore3120：3.8％ 82160の115440のオーバーラップ：140.5％ 最大のオーバーラップ：38