Python - 仅当条件适用时组合

Question

假设我有一个巨大的元组列表：

tuples = ([1, 2], [2, 1], [3, 2], [25, 73], [1, 3]...)

截至目前，该列表有 360000 个元素（它们是互质数列表）。我需要组合 3 个元组，这样每个组合上只有 3 个不同的数字，例如：

([2, 1], [3, 1], [3, 2])
([2, 1], [5, 1], [5, 2])

在生成组合列表时，我需要丢弃具有 4 个或更多不同数字的组合。

如果我尝试暴力破解并测试每个组合，我最终会得到360000 choose 3哪些7.77 * 10^15可能的组合进行测试。

编辑：我试图解决的问题是：

找到以下形式的互质对的所有组合：

(a, b), (a, c), (b, c)

对于 c < 120000

我采取的步骤：

1. 为两个数字都小于 120000 的所有 Coprime 对生成三叉树
2. （问题 - 生成组合，暴力破解是行不通的）

Answer 1

让我们制作一个将所有较大元素映射到元组中较小元素的集合字典：

d = {}
for tup in tuples:
    # here you may limit max(tup) to 120000
    d.setdefault(min(tup), set()).add(max(tup))

# {1: {2, 3}, 2: {3}, 25: {73}}

这也消除了所有对称对：(1, 2), (2, 1)。

然后搜索所有工作组合：

for a, bc in d.iteritems():
    for b, c in it.combinations(sorted(bc), 2):
        if b in d and c in d[b]:
            print(a, b, c) # or yield or append to a list

应该比你的蛮力还快……