I have an array of size n. Each element can hold any integer as long as the following properties holds:
1) All elements are non-negative
2) sum(array[0,i+1])<i for 0<=i<n
3) sum(array)=n-1
Let's call such an array a bucket.
I need to come up with a procedure that will generate the next bucket.
We can assume the first bucket is {0,0,0...n-1}
Example: For n=5, some possible combinations are
[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]
I'm having trouble coming up with a procedure that hits all the possible combinations. Any hints/tips? (Note I want to generate the next bucket. I'm not looking to print out all possible buckets at once)
You can use a simple backtracking procedure. The idea is to keep track of the current sum and the current index i. This would allow you to express the required constrains.
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)