我正在寻找一种算法，通过一次选择 6 个值来有效地生成数据集的所有三个值组合。
我正在寻找一种算法来有效地生成一小组 6 元组，这些 6 元组累积地表达数据集的所有可能的 3 元组组合。
例如，计算 6 张牌的扑克牌手牌，表示所有可能的 3 张牌组合。
例如，给定一个数据集：
['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']
这涵盖了三值组合：
('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（范围（26），sextuplets（范围（26））） 数据集中的所有三元组：2600 来自 sxt 的三胞胎总数：5720 六倍数：286 错过 2600 次中的 0 次：0.0% HitOnce 2288 的 2600：88.0% HitMore 312 of 2600: 12.0% 2600 的重叠 3120：120.0% 最大重叠：11 >>> check_coverage（范围（40），sextuplets（范围（40））） 数据集中的所有三元组：9880 来自 sxt 的三胞胎总数：22800 六倍数：1140 错过 9880 次中的 0 次：0.0% 9880 中的 HitOnce 9120：92.3% HitMore 760 of 9880: 7.7% 重叠 12920 与 9880：130.8% 最大重叠：18 >>> check_coverage（范围（80），sextuplets（范围（80））） 数据集中的所有三元组：82160 来自 sxt 的三胞胎总数：197600 六倍数：9880 错过 82160 次中的 0 次：0.0% 82160 中的 HitOnce 79040：96.2% 点击更多 82160 中的 3120：3.8% 82160 的重叠 115440：140.5% 最大重叠：38