Integer Partition Algo - Converting from Java to Python

Question

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!

Rohit Jain · Accepted Answer · 2012-11-23 18:00:43Z

1

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.

edited Nov 23, 2012 at 18:00

answered Nov 23, 2012 at 17:54

Rohit Jain

214k45 gold badges419 silver badges534 bronze badges

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

Comments

NPE · Accepted Answer · 2012-11-23 17:55:35Z

0

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)

answered Nov 23, 2012 at 17:55

NPE

503k114 gold badges970 silver badges1k bronze badges

Collectives™ on Stack Overflow

Integer Partition Algo - Converting from Java to Python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related