从列表中获取所有成对组合

Question

例如，如果输入列表为

[1, 2, 3, 4]

我希望输出结果为。

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

如果可能的话，我想要一种比使用两个for循环的蛮力方法更好的解决方案。我该如何实现？

- Utsav Vakil

---

对于n个元素的集合，有2^n个成对组合。所有解决方案都需要指数级的时间来生成所有组合；嵌套的for循环将使您在最快的解决方案的常数因子内。除非您只是在寻找更紧凑的东西。 - lungj

@lungj 我已经有一段时间没有正式学习数学了，但是你从哪里得到了 2^n 这个数字？有序对是 4! / (4 - 2)!（等于12），而无序对则是 4 选 2（等于6）。 - brianpck

@brianpck 哎呀，不好意思。是的，你说得对。它的时间复杂度是O(n^2)。 - lungj

Answer 1

尽管先前的答案会给出所有成对排序，但所期望的示例结果似乎意味着您想要所有无序对。使用 itertools.combinations 可以实现此目的。

>>> import itertools
>>> x = [1,2,3,4]
>>> list(itertools.combinations(x, 2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

与其他结果相比：

>>> list(itertools.permutations(x, 2))
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

- brianpck

Answer 2

import itertools

x = [1,2,3,4]

for each in itertools.permutations(x,2):
    print(each)

注意，itertools是一个生成器对象，这意味着您需要对其进行迭代以获取所需的所有内容。“2”是可选的，但它告诉函数您想要每个组合中的数字数量。 您可以在此处阅读更多信息 编辑：

正如ForceBru在评论中所说，您可以解包生成器以打印，跳过for循环。但我仍然建议迭代它，因为您可能不知道生成的对象有多大。

print(*itertools.permutations(x, 2))

- MooingRawr

---

在Python 3.x中，可以使用print(*itertools.permutations(x, 2))，这甚至更短。 - ForceBru

@ForceBru 说得好，拆开来看，我想我也可以把它加到答案里，但我认为 OP 需要生成这些东西的原因一定是有的（也许是因为 OP 将在另一个函数调用中使用它们之类的）。 - MooingRawr

@ForceBru permutations 返回一个迭代器，但我相信解包它会创建一个（可能很大的）对象，这实际上可能会减慢整个过程（特别是如果需要交换）。 - lungj

除非您使用 itertools.combinations，否则此方法无法产生所需的输出。 - Stop harming Monica

@brianpck 我只是在比较两种方法的性能，都使用了内置的方法（即，我并不建议自己编写）。我用 timeit 运行了一个基准测试，使用 for 循环进行比较，并将其与无操作的元组解包版本进行了比较（因为我猜测 OP 并不仅仅是要打印出每个值）。在使用 x = list(range(5000)) 创建的列表上，元组解包版本在我的计算机上运行速度比未解包版本慢 3 倍。然而，对于小型列表，调用我的无操作函数所产生的开销超过了为整个元组分配内存的成本。 - lungj