help for recursive summing function

[wdsd]

My goal is to write a function that takes a number and returns the number of solutions for that number, a form along the lines of f(a) = x_0 + x_1 +...+ x_n = a. where n can be any number such that n < a. Another restriction that I'm trying to implement is the return of only sets with unique elements as solutions. For example, f(4) would return the sets {4}, {1,3}. {2,2} would not be included because it has non-unique elements (I'm also ignoring {0,4} and {0,1,3}).

So far I've been able to solve all pairs that add up to any number, but for triplets and beyond I'd like to use a recursive function, which has been problematic. Here's what I have so far:

global results
results = []
global temp
temp = []

def solve(n):
        for i in range(n,0,-1):
                if n == i:
                    results.append([i])
                else:                    
                    temp = [i]
                    loop(n, i,temp)
        
        return results
        

def loop(n, i, total):
        for j in range(min(total),0,-1):
            if i + j < n:
                temp.append(j)
                loop(n,temp)
            else:
                if i + j == n:
                    results.append([i,j])
                    temp.pop()
                else:
                    temp = []
            
print solve(4)

I'm not sure of my use of global variables or recursive functions but I do know it's not working. Pointers or suggestions would be most helpful.

Thanks

[jlm699]

No, you're not using global variables correctly. Here's the correct way to use a global variable:

# This is the global scope
my_var = 'Hi'

def my_function( input ):
    # This is inside the function's scope
    global my_var
    # This pulls my_var into the scope of the function

With that being said, using globals is not a good idea. You should restructure your code so that you don't need globals.

Here's a rewrite of your first function:

def solve(n):
    results = []
    for i in range(n,0,-1):
        if n == i:
            results.append([i])
        else:                    
            temp = [i]
            loop(n, i,temp)

    return results

There's no need to use a "global" results list since you're only making use of it within that function. Here's some info on recursive functions.

[BigTurtle]

This is a cute combinatorial problem. A set of integers >0 that adds up to an integer A >= 0 is called a partition of A. You want to generate all partitions of A into N distinct parts. Call this "Problem A."

A little thought shows that if you subtract 1,2,3,... from the distinct parts you get a much easier problem: to find a partition of B = A - (N)(N+1)/2 into at most N parts. Call this "Problem B."

On the left in the list below are all the solutions to Problem A with A=18, N=4; on the right are the solutions to Problem B with B=8, N=4. You get the solutions to Problem A by adding [4,3,2,1] to the solutions to problem B. Note that 4+3+2+1 = 10 = (4)(5)/2, as stated.

1: [ 12, 3, 2, 1 ] [ 8, 0, 0, 0 ]
2: [ 11, 4, 2, 1 ] [ 7, 1, 0, 0 ]
3: [ 10, 5, 2, 1 ] [ 6, 2, 0, 0 ]
4: [ 10, 4, 3, 1 ] [ 6, 1, 1, 0 ]
5: [ 9, 6, 2, 1 ] [ 5, 3, 0, 0 ]
6: [ 9, 5, 3, 1 ] [ 5, 2, 1, 0 ]
7: [ 9, 4, 3, 2 ] [ 5, 1, 1, 1 ]
8: [ 8, 7, 2, 1 ] [ 4, 4, 0, 0 ]
9: [ 8, 6, 3, 1 ] [ 4, 3, 1, 0 ]
10: [ 8, 5, 4, 1 ] [ 4, 2, 2, 0 ]
11: [ 8, 5, 3, 2 ] [ 4, 2, 1, 1 ]
12: [ 7, 6, 4, 1 ] [ 3, 3, 2, 0 ] *
13: [ 7, 6, 3, 2 ] [ 3, 3, 1, 1 ]
14: [ 7, 5, 4, 2 ] [ 3, 2, 2, 1 ]
15: [ 6, 5, 4, 3 ] [ 2, 2, 2, 2 ]

To understand Problem B recursively, think about what you have to do to generate all possibilities for a given element of the solution. Suppose you have already generated the vector [3] (see * above). What comes next?

Well, the next element can't be more than 5, because there are only 5 left out of the 8 that you started with. Also it can't be more than 3 because you're working in non-increasing order. So the next element is at most the minimum of (unplaced remainder) and (previous element).

Also the next element can't be less than 2, because you have to fit the remaining 5 into 3 positions and, again, you're working in non-increasing order. So the next element is at least the smallest integer >= (unplaced remainder)/(number of remaining elements). For this we'll use the ceiling function.

Now that you know the max and min values of the next element, all you have to do is loop over the possibilities. Each possibility goes in as next element in your solution vector, after which you see what's left and where it should go, and make a recursive call to generate the rest of the possibilities.

The docstring at the beginning of Generate() is extremely important, because it states exactly what you have to do and what all the variables mean. Once you write it, the function is obvious (almost :P ).

Whenever your vector is complete, call a result function to deal with it. There are lots of complicated things you might want to do... all I've done is write a print routine to generate the output I showed you above. Also I have solved Problem A there by "adding water" to the results of Problem B.

Bear in mind that the results are generated one at a time and function Result() is called exactly once for each, so if you want to deal with them you have to do it in Result(), one result at a time.

Here's the program.

import math

def GetParts(A, N):
    global ResultCount

    ResultCount = 0
    B = A - N*(N+1)/2
    if B > 0:
        Generate(B, N-1, B)

def Generate(Rem, Ind, Prev):
    ''' Following the existing elements of V (if any),
        generate all partitions of Rem into at most Ind parts,
        with parts in non-increasing order, and no part greater than Prev.
    '''

    if Ind < 0:
        Result()
    else:
        MaxElt = min([Prev, Rem])
        MinElt = int(math.ceil(Rem/(Ind+1.0)))
        for Elt in range (MaxElt, MinElt-1, -1):
            V.append(Elt)
            Generate(Rem-Elt, Ind-1, Elt)
            V.pop()

def Result(): # For demo
    global ResultCount

    ResultCount += 1
    N = len(V)
    print repr(ResultCount) + ': [',
    for J in range(N-1):
        print repr(V[J] + N - J) + ',',
    print repr(V[N-1] + 1) + ' ] [',
    for J in range(N-1):
        print repr(V[J]) + ',',
    print repr(V[N-1]) + ' ]'

#--------------------

V = []
GetParts(18, 4)

I hope this isn't homework, because if so I have taken away your initiative. But if you're trying to learn how to do it, this little demo might help. Note that the entire solution takes just 9 lines.

The method I'm showing you is called recursive combinatorial generation. It's very powerful and has lots of interesting applications in computational mathematics.