2

目前，我正在输出列表中的所有素数组合以及该子集的乘积，如下所示：

from operator import mul
from itertools import combinations

primes = [2, 3, 5, 7, 11]

for r in range(1,len(primes)):
    for combo in combinations(primes,r+1):
        print combo, reduce(mul, combo)

哪个输出

(2,) 2
(3,) 3
(5,) 5
(7,) 7
(11,) 11
(2, 3) 6
(2, 5) 10
(2, 7) 14
(2, 11) 22
(3, 5) 15
(3, 7) 21
(3, 11) 33
(5, 7) 35
(5, 11) 55
(7, 11) 77
(2, 3, 5) 30
(2, 3, 7) 42
(2, 3, 11) 66
(2, 5, 7) 70
(2, 5, 11) 110
(2, 7, 11) 154
(3, 5, 7) 105
(3, 5, 11) 165
(3, 7, 11) 231
(5, 7, 11) 385
(2, 3, 5, 7) 210
(2, 3, 5, 11) 330
(2, 3, 7, 11) 462
(2, 5, 7, 11) 770
(3, 5, 7, 11) 1155
(2, 3, 5, 7, 11) 2310

现在假设我们正在查看以下块：

(2, 5, 7) 70
(2, 5, 11) 110
(2, 7, 11) 154
(3, 5, 7) 105
(3, 5, 11) 165
(3, 7, 11) 231
(5, 7, 11) 385
(2, 3, 5, 7) 210
(2, 3, 5, 11) 330

举个例子，我想遍历乘积 <110 的所有组合。这里的第一个“端点”出现在 (2,5,11)，因为乘积是 110。

问题是，如果我此时中断，它会认为我正在尝试中断所有长度为 3 的元组并继续前进到 (2,3,5,7)，从而跳过其他有效的 (3,5,7 ) 产品 <110。另一方面，如果我只是在这一点上继续，我最终会遍历大量我知道会浪费时间的元组。如果我知道 (2, 5, 11) 太大，那么 (2, 7, 11) 显然也会太大，我不应该评估它。

我不确定我的问题是否清楚，但是是否有另一种方法可以生成输出顺序更符合我的结构的组合？

4

1 回答 1

1

“问题”是生成器以特定顺序combinations发出所有长度的元组。r您希望它们以不同的顺序出现。因此，您需要编写自己的combinations生成器。

这些类型的生成器通常是递归编写的：r要从您那里发出所有长度的组合，i首先删除一个元素——第一个元素——然后(r-1)从其余元素中递归地发出所有长度的组合。

现在，您要做的是在乘积太大时立即停止递归，这样您就不会发出不必要的元组。不幸的是，编写这种生成器的常用方法不允许您这样做，因为字典顺序与“按乘积递增的顺序”不同。

这意味着你必须找到一种不同的递归方式，每次都会增加数字的乘积。稍加思考应该会带您了解以下算法：

  • 从尽可能小的元组开始。
  • 对于元组的每个索引，尝试将其“向上碰撞”到下一个素数。仅在以下情况下执行此操作
    • 产品仍然低于限制，并且
    • 元组保持排序顺序。
  • 这给了你一个新的元组开始，所以递归它。

这可以如下实现。

from operator import mul
primes = [2, 3, 5, 7, 11]
primes_inorder = dict(zip(primes, primes[1:]))

def my_combinations(primes, r, N, start=None, prod=None):
    """Yield all sorted combinations of length `r`
       from the sorted list `primes`."""
    if start is None:
        start = primes[:r]
        prod = reduce(mul, start)
        if prod > N: return

    yield start

    for i, v in enumerate(start):
        next_v = primes_inorder.get(v, None)
        if next_v is None or (i+1 < r and next_v > start[i+1]):
            continue

        new_prod = prod / v * next_v
        if new_prod > N:
            continue

        new_start = start[:]
        new_start[i] = next_v
        for combination in my_combinations(primes, r, N, start=new_start, prod=new_prod):
            yield combination
于 2012-04-17T20:28:01.193 回答