Make recursive function of for loops and if statements into iterative function

Question

The challenge was to find all possible combinations of numbers less than N whose sum equals N. For instance, when N is equal to:

2
- 1+1 - 1 way
3
- 2+1
- 1+1+1 - 2 ways
4
- 3+1
- 2+2
- 2+1+1
- 1+1+1+1 - 4 ways

and so on...

Now creating it in python, to understand the pattern I drafted this code 1st:

N=5
for d in drange(0,N,1):
    if N-d*4>=0:
        for c in drange(0,N,1):
            if N-d*4-c*3>=0:
                for b in drange(0,N,1):
                    if N-d*4-c*3-b*2>=0:
                        for a in drange(0,N,1):
                            if N-d*4-c*3-b*2-a*1==0:
                                if sum([d,c,b,a])!=1:
                                    print d,c,b,a                            
                    else: break
            else:break
    else:break

Then I changed the code to this where this worked for N = 6 and below:

N=6
for e in drange(0,N,1):
    if N-e*5>=0:
        C0 = N-e*5
        for d in drange(0,N,1):
            if C0-d*4>=0:
                C1 = C0-d*4
                for c in drange(0,N,1):
                    if C1-c*3>=0:
                        C2 = C1-c*3
                        for b in drange(0,N,1):
                            if C2-b*2>=0:
                                C3 = C2-b*2
                                for a in drange(0,N,1):
                                    if C3-a*1==0:
                                        if sum([e,d,c,b,a])!=1:
                                            print e,d,c,b,a                            
                            else: break
                    else:break
            else:break
    else:break

Next Version incorporated arrays to keep track of numbers and save computation space:

N=6
Nums = drange2(6-1,-1,-1)
Vals = [0]*6
Vars = [0]*6
for Vars[0] in drange(0,N,1):
     if N-Vars[0]*Nums[0]>=0:
         Vals[0] = N-Vars[0]*Nums[0]
         for Vars[1] in drange(0,N,1):
             if Vals[0]-Vars[1]*Nums[1]>=0:
                 Vals[1] = Vals[0]-Vars[1]*Nums[1]
                 for Vars[2] in drange(0,N,1):
                     if Vals[1]-Vars[2]*Nums[2]>=0:
                         Vals[2] = Vals[1]-Vars[2]*Nums[2]
                         for Vars[3] in drange(0,N,1):
                             if Vals[2]-Vars[3]*Nums[3]>=0:
                                 Vals[3] = Vals[2]-Vars[3]*Nums[3]
                                 for Vars[4] in drange(0,N,1):
                                     if Vals[3]-Vars[4]*Nums[4]==0:
                                         if sum([Vars[0],Vars[1],Vars[2],Vars[3],Vars[4]])!=1:
                                             print Vars                           
                             else: break
                     else:break
             else:break
     else:break

Then I thought to make this code functional where N is 100, I made it recursive...

N=48
Nums = drange2(N-1,-1,-1)
Vals = [0]*N
Vars = [0]*(N-1)
count=0
def sumCombos(Number,i):
    if i==0:
        global count        
        for Vars[i] in xrange(0,i+2,1):
            z = Number-Vars[i]*Nums[i]
            if z>=0:
                Vals[i] = z
                sumCombos(Number,i+1)
            else: break
    elif i<Number-2:
        for Vars[i] in xrange(0,i+1,1):
            z = Vals[i-1]-Vars[i]*Nums[i]
            if z >=0:
                Vals[i]=z
                sumCombos(Number,i+1)
            else: break
    elif i==Number-2:
        for Vars[i] in xrange(0,i+3,1):
            if Vals[i-1]-Vars[i]*Nums[i]==0:
                count+=1
sumCombos(N,0)
print count

PROBLEM: It takes too much time because of 1000000+ method calls, so is there a way I can make this iterative where it creates that previous cascade effect without me typing that all? I searched the website and others on how to make a recursive function involving for-loops and if statements iterative, but no luck with this particular one. Please offer any wisdom -- Shaha3

JBernardo · Accepted Answer · 2012-07-13 04:53:44Z

5

Why do you want it to be recursive?

>>> from itertools import chain, combinations_with_replacement
>>> n = 7
>>> [i for i in chain.from_iterable(
       combinations_with_replacement(range(1, n), k)
       for k in range(2, n+1))
     if sum(i) == n]

[(1, 6), (2, 5), (3, 4), (1, 1, 5), (1, 2, 4), (1, 3, 3), (2, 2, 3), (1, 1, 1, 4), (1, 1, 2, 3), (1, 2, 2, 2), (1, 1, 1, 1, 3), (1, 1, 1, 2, 2), (1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 1, 1, 1)]

This problem grows with n! so, it'll take a lot of time for big numbers.

edited Jul 13, 2012 at 4:53

answered Jul 13, 2012 at 4:41

JBernardo

33.6k13 gold badges92 silver badges120 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

mgilson Over a year ago

This doesn't get all of them (where is (1,1,1,1,1,1,1))?

JBernardo Over a year ago

@mgilson oh right... combinations_with_replacement made it work :)

dolaameng · Accepted Answer · 2012-07-13 04:42:37Z

I guess you are talking about integer partitioning problem (wiki: http://en.wikipedia.org/wiki/Partition_(number_theory) ) It can be done either an iterative way or a recursive way, though there could be a depth limit on the recursive method. Here are my implementations


def partitions(n):
    def next(seq):
        L = len(seq)
        ## start from L-2 element, must have at least one element in suffix
        for i in range(L-2, -1, -1):
            if seq[i-1] and seq[i-1] > seq[i]: break
        remainder = n - sum(seq[:i+1]) - 1
        return seq[:i] + [seq[i]+1] + [1 for _ in range(remainder)]
    start, end = [1 for _ in range(n)], [n]
    seq = start
    while True:
        yield seq
        if seq >= end: break
        seq = next(seq)


# test cases
if __name__ == '__main__':
    ## test partitions
    assert list(partitions(4)) == [[1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]]
    assert list(partitions(5)) == [
        [1, 1, 1, 1, 1], 
        [2, 1, 1, 1], [2, 2, 1], 
        [3, 1, 1], [3, 2], 
        [4, 1], 
        [5]]

    print 'all tests passed'

Collectives™ on Stack Overflow

Make recursive function of for loops and if statements into iterative function

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related