python - 从 Python 列表中删除公因子

Question

我有一份清单清单

itertools.product(range(5), repeat=3)

这使

[[0 0 0]
 [0 0 1]
 [0 0 2]
 [0 0 3]
 [0 0 4]
 [0 1 0]
 [0 1 1]
... etc]

我想删除所有具有公共整数因子的列表，除了 0 和 1 的平凡情况，因为那样会匹配所有列表。例如 [0 0 2] 是 [0 0 1] 乘以 2，所以我想删除 [0 0 2]。另一个例子是 [3 3 3]，它是 [1 1 1] 乘以 3，所以我想删除 [3 3 3]。最有效的方法是什么？

标签： python

Answer 1

听起来您想要所有不共享公因数的组合（显然，除了 1）。例如：[2, 3, 4]应该在您的列表中，因为您不能考虑除一个以外的所有人共享的单个数字。[2,4,0]另一方面可以认为是2 * [1, 2, 0]。您可以使用math.gcd来查找 GCD — GCD 是关联的，因此您可以嵌套它（或reduce()用于通用解决方案）。

from itertools import product
from math import gcd
from functools import reduce

test = lambda p: reduce(gcd, p) == 1

[p for p in product(range(5), repeat=3) if test(p)]

结果

[(0, 0, 1),
 (0, 1, 0),
 (0, 1, 1),
 (0, 1, 2),
 (0, 1, 3),
 (0, 1, 4),
 (0, 2, 1),
 (0, 2, 3),
 ...
 (4, 2, 3),
 (4, 3, 0),
 (4, 3, 1),
 (4, 3, 2),
 (4, 3, 3),
 (4, 3, 4),
 (4, 4, 1),
 (4, 4, 3)]

由于 gcd 的工作方式，您需要将其[0,0,0]视为特殊情况。