算法以相同的总和遍历固定大小的正整数列表 [英] algorithm to iterate through fixed size positive integer lists with the same sum

问题描述

我正在寻找一种快速且内存高效的算法，以给定总和(N)遍历所有相同大小(S)的正整数的所有可能列表.

I am looking for a fast and memory efficient algorithm to iterate through all possible lists of positive integers of the same size (S) with a given sum (N).

例如，如果S = 3且N = 4，结果将是(我的算法效率很低):

for example if S = 3 and N = 4 the result would be (i have a really inefficient algo):

[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片.如果我还可以为列表中的每个单独的值设置最大值，那么该算法将是完美的.

Not necessarily in that order. Another way to look at it is how to cut the number N into S pieces. The algorithm would be perfect if i could also set a maximum for each separate value in the lists.

我将使用它以与product(*indices)产生的顺序不同的顺序遍历多维数组.

I would use this to run through multidimensional arrays in a different order than produced by product(*indices).

生成所有索引组合并按总和对它们进行排序也将太慢/消耗内存.

Also generating all index combinations and sorting them by the sum would be too slow/memory consuming.

推荐答案

找到了一个解决方案:它基于这样的思想:正数N是一行单位，将它们拆分为S个部分是放置(S -1)列表中的分隔符. 这些分隔符可以使用combinations(range(N + S - 1), S - 1)进行迭代.下一步是计算分隔符之前，之间和之后的单位数:

Found a solution: it is based on the idea that a positive number N is a line of units and splitting them in S pieces is a matter of putting (S-1) separators in the list. These separators can iterated with combinations(range(N + S - 1), S - 1). The next step is to calculate the number of units before, between and after the separators:

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版本:

When you want to limit each item in the result you can filter unwanted out (surely not optimal, but i wanted to use combinations because it is probably implemented in C, and therefore probably much faster than anything i can come up with in python). The simpole version:

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

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

And the faster but more complicated version:

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)

顺便说一句:从臀部:您可以通过遍历S(大小):来生成整数分区问题的解决方案，如下所示:

BTW: from the hip: you can generate the solution to the integer partitioning problem by iterating over S (size): as in:

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，则对具有不同顺序的相同分区加倍.

I adapted the combinations() iterator a bit to not give zeros. It dedoubles for same partitions with different orders if order=False.

这篇关于算法以相同的总和遍历固定大小的正整数列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！