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 选择 3，这是 7.77 * 10^15 要测试的可能组合。

编辑:我要解决的问题是:

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

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

对于 c < 120000

我采取的步骤:

1. 为所有小于 120000 的互质对生成三元树
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

应该比你的蛮力更快......