itertools.combinations在Python中如何扩展？

Question

我正在用暴力破解的方法来寻找一个谜题的扩展组合。

我想生成大量的组合，然后测试每一个组合，看看它们是否符合某些条件。为了生成这些组合，我使用了Python里非常好用的itertools库，这样我就能得到一个可以逐个检查的组合迭代器。

这个方法很快就能返回结果，给我提供了91390个组合供我检查：

itertools.combinations(range(1, 40), 4)

这个过程大约需要几分钟，结果给了我198792594个组合来测试：

itertools.combinations(range(1, 122), 5)

当我进入下一个层级时，我需要解决这个问题：

itertools.combinations(range(1, 365), 6)

当我处理364个元素的6个组合时，所需的时间非常长，简直是漫长。我是不是在要求太多的组合？这个过程是如何扩展的？

Answer 1

根据itertools的文档，返回的项目数量是用公式计算的：n! / r! / (n-r)!，当0 <= r <= n时有效；如果r大于n，则返回的数量是零。

内存使用量很小——只需要足够存储n个项目的集合和长度为r的结果元组。

Answer 2

你可以这样计算这些数字：

1. 先去 google.com
2. 输入“40 选 4”
3. 输入“121 选 5”
4. 输入“364 选 6”

想了解具体的公式，可以查看维基百科。

这个计算方式和阶乘函数的增长方式是一样的。

Answer 3

你在问的是从365个选项中选6个的组合数，这个计算公式是：365选择6 = (365 * 364 * ... * 360) / (6 * 5 * ... * 2 * 1) = 3,151,277,509,380种组合。这真的是一个非常多的组合数。用Python在你的电脑上循环处理30万亿个元素，根本不可能。

如果你只是想知道总共有多少种组合，可以直接用一个公式来计算，而不需要考虑所有的组合，具体的公式可以在维基百科上找到。

补充一下：我刚刚看了这个问题，似乎你是想通过考虑所有可能的权重组合来解决它。但是，直接穷举所有组合显然行不通——你需要想出一个更聪明的解决办法。