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

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]

我无法想出一个可以满足所有可能组合的程序。有 hints/tips 吗？（注意我想生成下一个桶。我不想一次打印出所有可能的桶）

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

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

Coming with a procedure to generate an array with special properties

algorithm

pseudocode