CODEWITHSUNDEEP
algorithmpseudocode
Mike
Mike

Reputation: 331

Coming with a procedure to generate an array with special properties

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)

Upvotes: 2

Views: 63

Answers (1)

sve
sve

Reputation: 4356

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)

test run

Upvotes: 2

Related Questions