current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite
1

I've come across a question when I was looking at a bunch of algorithms for fun. The algorithm that I solved (in Java) asks me to list all the partitions of an integer. So the partitions of 4 should receive the following printed output:

4 , 3+1, 2+2, 2+1+1, 1+1+1+1

This is my code in Java:

 public static void partition(int n) {
        partition(n, n, "");
    }
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            StdOut.println(prefix);
            return;
        }

        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n-i, i, prefix + " " + i);
        }
    }

However, when I tried to convert my Java code to Python, I get the "recursion depth exceed" error. Here it is:

def partition_rec(N):
    def part(N,maximum = N, prefix = ""):
        if(N==0):
            print(prefix)
            return
        for i in range(N-1):
           part(N-i,i,prefix + " " + str(i))
    return part(N)

Could someone help me out? Thanks!

share|improve this question

2 Answers 2

up vote 1 down vote

You have changed your for loop. In Java it is running in reverse direction. In python equivalent you are running it form 0 to N - 2.

Change your for loop to: -

for i in range(min(maximum, N), 0, -1):

to be exact. Since, loop is form n to 1.

-1 is the step value, and it runs the range in reverse.

share|improve this answer
    
It works! Thanks for the input. –  user1923 Nov 23 '12 at 18:00
    
@JeffreyTan.. You're welcome :) –  Rohit Jain Nov 23 '12 at 18:01
up vote 0 down vote

When I change your code to match the Java version, it works for me:

def partition_rec(N):
    def part(N,maximum = N, prefix = ""):
        if(N==0):
            print(prefix)
            return
        for i in range(min(maximum, N), 0, -1): # changed this line
           part(N-i,i,prefix + " " + str(i))
    return part(N)

partition_rec(4)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.