0

Considering the following code for Integer Partition:

int p (int n, int m)
{
    if (n == m)
        return 1 + p(n, m - 1);
    if (m == 0 || n < 0)
        return 0;
    if (n == 0 || m == 1)
        return 1;

    return p(n, m - 1) + p(n - m, m);

}

If I take an example p(7,3), what happens after function becomes p(7,0) & p(4,3)?

Monte San
  • 135
  • 2
  • 12
  • I really don't understand what help you want, can you please elaborate more. – Ratshiḓaho Wayne Jan 17 '16 at 12:15
  • @RatshiḓahoWayne I an stuck after getting the function p(7,0) and p(1,3). Now I have to substitute the return values according to the condition but where should I substitute them?Inside the function or is it the overall function value? – Monte San Jan 17 '16 at 12:20
  • Are you trying to trace a computation by hand and are confused by what your definition means? – John Coleman Jan 17 '16 at 12:37
  • What values did you start with? Telling us that p(7,0) and p(1.3) arise in the calculation is not very informative. Also -- this seems like homework. If so, you should mention that explicitly and hope for no more than a hint. – John Coleman Jan 17 '16 at 12:55
  • 1
    @JohnColeman NO, this isn't my homework..I was following this question from StackOverflow: http://stackoverflow.com/questions/14053885/integer-partition-algorithm-and-recursion [ the algorithm I posted in my question is from the given link]..The example I am taking is from one of the top rated answers..I am not getting how the values like 3+3+1, 3+2+1+1 etc are generated from the above function. – Monte San Jan 17 '16 at 13:06
  • The link you provided (http://stackoverflow.com/questions/14053885/integer-partition-algorithm-and-recursion) actually has a great explanation in the accepted answer. Also, you might try computing a smaller example by hand, like `p(3,3)`. – גלעד ברקן Jan 17 '16 at 13:30

1 Answers1

3

If you have Python you can play around with this:

def p(n,m):
    if n == m:
        return 1 + p(n,m-1)
    elif m == 0 or n < 0:
        return 0
    elif n == 0 or m == 1:
        return 1
    else:
        return p(n,m-1) + p(n-m,m)

def tupleFromString(s):
    #converts a string like `(3,7)` to the correspoding int tuple
    s = s.strip()
    arguments = s[1:len(s)-1].split(',')
    return tuple(int(i) for i in arguments)

def toString(t):
    #converts an int-tuple to a string, without the spaces
    return str(t).replace(' ','')

def expandOnce(s):
    s = s.strip()
    if s.startswith('p'):
        n,m = tupleFromString(s[1:])
        if n == m:
            return '1 + p' + toString((n,m-1))
        elif m == 0 or n < 0:
            return '0'
        elif n == 0 or m == 1:
            return '1'
        else:
            return 'p' + toString((n,m-1)) + ' + p' + toString((n-m,m))
    else:
        return s

def expandLine(line):
    return ' + '.join(expandOnce(term) for term in line.split('+'))

def expand(s):
    firstLine = True
    k = len(s)
    prefix = s + ' = '
    while 'p' in s:
        if firstLine:
            firstLine = False
        else:
            prefix = ' '*k + ' = '
        s = expandLine(s)
        print(prefix + s)
    print(prefix + str(sum(int(i) for i in s.split('+'))))

p(m,n) is a direct implementation of the function, and expand displays the steps as strings:

>>> p(4,3)
4
>>> expand('p(4,3)')
p(4,3) = p(4,2) + p(1,3)
       = p(4,1) + p(2,2) + p(1,2) + p(-2,3)
       = 1 + 1 + p(2,1) + p(1,1) + p(-1,2) + 0
       = 1 + 1 + 1 + 1 + p(1,0) + 0 + 0
       = 1 + 1 + 1 + 1 + 0 + 0 + 0
       = 4

The logic of this is as follows. If you want to know what p(4,3) is, you consult the definition. p(4,3) has n = 4 and m = 3, so you need to use that last clause of the definition. This tells you that

p(4,3) = p(4,3-1) + p(4-3,3)
       = p(4,2) + p(1,3)

That doesn't help unless you know what p(4,2) and p(1,3) are so you go back to the definition and find that p(4,2) = p(4,1) + p(2,2) and p(1,3) = p(1,2) + p(-1,2). Combining this with the above, you now know that 

p(4,3) = p(4,3-1) + p(4-3,3)
       = p(4,2) + p(1,3)
       = p(4,1) + p(2,2) + p(1,3) + p(1,2)

at each stage, if there is a term which looks like p(m,n) -- you go back to the definition and see what it means. You eventually hit basis cases such as p(4,1) = 1. Once all of the p are evaluated -- just add what is left (just a bunch of ones and zeros).

Similarly,

p(7,3) = p(7,2) + p(4,3)
       = p(7,1) + p(5,2) + p(4,2) + p(1,3)
       = 1 + p(5,1) + p(3,2) + p(4,1) + p(2,2) + p(1,2) + p(-2,3)
       = 1 + 1 + p(3,1) + p(1,2) + 1 + 1 + p(2,1) + p(1,1) + p(-1,2) + 0
       = 1 + 1 + 1 + p(1,1) + p(-1,2) + 1 + 1 + 1 + 1 + p(1,0) + 0 + 0
       = 1 + 1 + 1 + 1 + p(1,0) + 0 + 1 + 1 + 1 + 1 + 0 + 0 + 0
       = 1 + 1 + 1 + 1 + 0 + 0 + 1 + 1 + 1 + 1 + 0 + 0 + 0
       = 8
John Coleman
  • 51,337
  • 7
  • 54
  • 119