{0...k} 中 r 个整数的重复变化，总和为 u

Question

给定一组整数

x = {0...k}

，我需要找到最有效的算法来生成所有变化，并重复

r

整数

x

，总和为

u

。

我想

from itertools import product
import numpy as np
import pandas as pd

k = 10
r = 5
u = 12
x = np.arange(0, k+1)

prod = product(x, repeat=r)
df = pd.DataFrame(list(prod))
print(f"VR{x.size, r} = {df.index.size} = (k+1)^r = {(k+1)**r}\n")

df = df[df.sum(axis=1)==u]
print(df)

VR(11, 5) = 161051 = (k+1)^r = 161051

         0  1  2  3   4
32       0  0  0  2  10
42       0  0  0  3   9
52       0  0  0  4   8
62       0  0  0  5   7
72       0  0  0  6   6
...     .. .. .. ..  ..
146652  10  0  2  0   0
147742  10  1  0  0   1
147752  10  1  0  1   0
147862  10  1  1  0   0
149072  10  2  0  0   0

[1795 rows x 5 columns]

但是这是非常低效的，因为重复的变化总数是

VR(k+1, r) = (k+1)^r

并且会产生一个巨大的

df

。

有什么建议吗？

Answer 1

为了避免创建所有产生式，一旦无法再获得总和，您可以通过添加剩余值来完成 r 元组来退出。

这是一个执行此操作的简单 Python 函数。我没有将其执行时间与其他解决方案进行比较，但使用示例参数，当我运行它时，它会在 0.003 秒内返回一个列表。当然，打印这些条目也需要时间：

def solve(greatest, count, target):
    collected = [0] * count
    if count <= 0 or count == 1 and target > greatest:
        return
    
    def recur(count, target):
        if count == 1:  # base case
            collected[-1] = target
            yield tuple(collected)
            return
        i = count - 1
        # Clip the range to values that still allow solutions
        for val in range(max(0, target - i * greatest), min(target, greatest) + 1):
            collected[-count] = val
            yield from recur(i, target - val)
            
    yield from recur(count, target)

# example run
from time import time
start = time()
result = list(solve(10, 5, 12))
print("done", time() - start)
print(result)

Answer 2

虽然不是一个更聪明的基本算法，但你可以避免使用 Pandas，并且直接在 Numpy 中速度快 100 倍，从而避免形成巨大的 DF 和 List：

res = [y for y in prod if sum(y) == u]