迭代具有相同和的固定大小正整数列表的算法

Question

我正在寻找一种快速高效的算法，以给定的和（N）遍历所有可能的相同大小的正整数列表

例如，如果S=3和N=4，结果将是（我有一个非常低效的算法）：

[0, 0, 4]
[0, 1, 3]
[0, 2, 2]
[0, 3, 1]
[0, 4, 0]
[1, 0, 3]
[1, 1, 2]
[1, 2, 1]
[1, 3, 0]
[2, 0, 2]
[2, 1, 1]
[2, 2, 0]
[3, 0, 1]
[3, 1, 0]
[4, 0, 0]

不一定按那个顺序。另一种看待它的方式是如何将数字N切成S段。如果我还可以为列表中的每个单独值设置一个最大值，那么该算法将是完美的

我将使用它以不同于product(*indices)生成的顺序运行多维数组

此外，生成所有索引组合并按总和对它们进行排序也会太慢/占用内存

Answer 1

我认为这是最简单的方式：

def elect(S,N,List):
    result_list = []
    for list_val in List:
        if sum(list_val) == N:
            if len(list_val) == S:
                result_list.append(list_val)

    return result_list

对于100万个列表，这在1秒内有效。如果您想加快速度，可以使用其他If语句，例如If sum（list_val[0:N/2]）>；N或len（列表值）/2>；S:这样的陈述可以更快地发现情况

另一种方法是对列表进行排序并查找前N个数字的总和。如果大于您想要的值，您可以选择这些列表

Answer 2

找到了一个解决方案：它基于一个想法，即正数N是一行单位，将它们分成S个部分就是将（S-1）分隔符放入列表中。 这些分隔符可以使用combinations(range(N + S - 1), S - 1)进行迭代。下一步是计算分离器之前、之间和之后的单元数：

def partition(N, size):
    n = N + size - 1
    for splits in combinations(range(n), size - 1):
        yield [s1 - s0 - 1 for s0, s1 in zip((-1,) + splits, splits + (n,))]

当您想限制结果中的每一项时，您可以过滤掉不需要的内容（当然不是最优的，但我想使用combinations，因为它可能是用C实现的，因此可能比我用python所能想到的任何东西都要快）。simpole版本：

def sized_partition_slow(N, sizes):
    size = len(sizes)
    n = N + size - 1
    for splits in combinations(range(n), size - 1):
        result = [s1 - s0 - 1 for s0, s1 in zip((-1,) + splits, splits + (n,))]
        if all(r < s for r, s in zip(result, sizes)):
            yield result

以及更快但更复杂的版本：

def sized_partition(N, sizes):
    size = len(sizes)
    n = N + size - 1
    for splits in combinations(range(n), size - 1):
        result = []
        for s, s0, s1 in zip(sizes, (-1,) + splits, splits + (n,)):
            r = s1 - s0 - 1
            if r >= s:
                break
            result.append(r)
        else:
            yield result

我将此用作早期测试：

for indices in partition(4, 3):
    assert sum(indices) == 4
    assert all(0 <= i for i in indices)

for indices in sized_partition(4, [3, 3, 3]):
    assert sum(indices) == 4
    assert all(0 <= i < 3 for i in indices)

顺便说一句：从hip：您可以通过迭代S（size）：生成整数分区问题的解决方案，如：

def integer_partition(N, order=False):
    result = set()
    for size in range(1, N+1):
        for splits in combinations(range(1, N), size - 1):
            if order:
                p = tuple(s1 - s0 for s0, s1 in zip((0,) + splits, splits + (N,)))
            else:
                p = tuple(sorted(s1 - s0 for s0, s1 in zip((0,) + splits, splits + (N,))))
            result.add(p)
    return sorted(result, key=lambda r: (len(r), r))

我对combinations()迭代器进行了一些调整，使其不给零。如果order=False，它会对具有不同顺序的相同分区进行加倍