algorithm - 带有生成具有特殊属性的数组的过程

Question

我有一个大小为 n 的数组。只要满足以下属性，每个元素都可以包含任何整数:

1) All elements are non-negative
2) sum(array[0,i+1])<i for 0<=i<n 
3) sum(array)=n-1

我们称这样的数组为桶。

我需要想出一个程序来生成下一个桶。

我们可以假设第一个桶是 {0,0,0...n-1}

示例:对于n=5，一些可能的组合是

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

我在想出一个能满足所有可能组合的过程时遇到了麻烦。任何提示/技巧？ (注意我想生成下一个桶。我不想一次打印出所有可能的桶)

Answer 1

您可以使用简单的回溯过程。这个想法是跟踪当前的 sum 和当前的索引 i。这将允许您表达所需的约束。

n = 5
a = [0] * n


def backtrack(i, sum):
    if i > 0 and sum > i-1:
        return
    if i == n:
        if sum == n-1:
            print(a)
        return
    for e in range(n-sum):
        a[i] = e
        backtrack(i + 1, sum+e)

backtrack(0, 0)

test run