In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. If order matters, the sum becomes a composition. For example, 4 can be partitioned in five distinct ways:
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
The order-dependent composition 1 + 3 is the same partition as 3 + 1, while 1 + 2 + 1 and 1 + 1 + 2 are the same partition as 2 + 1 + 1.
If we have a partition of n, we can reduce it to a partition of n-1 in a canonical way by subtracting one from the smallest item in the partition. E.g. 1+2+3 => 2+3, 2+4 => 1+4. This algorithm reverses the process: for each partition p of n-1, it finds the partitions of n that would be reduced to p by this process. Therefore, each partition of n is output exactly once, at the step when the partition of n-1 to which it reduces is considered.
public class Partition {
public static void partition(int n) {
partition(n, n, "");
}
public static void partition(int n, int max, String answer) {
if (n == 0) {
System.out.println(answer.substring(1));
return;
}
for (int i = Math.min(max, n); i >= 1; i--) {
partition(n-i, i, answer + "+" + i);
}
}
public static void main(String[] args) {
int N = 4;
partition(N);
}
}
The purpose of the substring() function on line number 7 is to remove the ‘+’ sign at beginning of each line of output. As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.
you can trip extra buffer “max”, below way, also fetches the same solution and its slightly more readable….your thoughts?
public static void partition(int n, String answer) { if (n == 0) { System.out.println(answer.substring(1)); return; } for (int i = n; i >= 1; i--) { partition(n-i, answer + "+" + i); } } public static void main(String[] args) { int n = 5; partition(n,""); }I agree that it’s slightly more readable and would save a bit of memory as well, but, it would be slightly more expensive in terms of time also.
I modified both the recursive version to add a counter as follows:
With max
public class PartitionRecrusive { private static int c = 0; public static void partition(int n) { partition(n, n, ""); } public static void partition(int n, int max, String prefix) { if (n == 0) { System.out.println(prefix.substring(1)); return; } for (int i = Math.min(max, n); i >= 1; i--) { c=c+1; partition(n-i, i, prefix + "+" + i); } } public static void main(String[] args) { int N = 4; partition(N); System.out.println(c); } }Without max
class Partition{ public static int c=0; public static void partition(int n, String answer) { if (n == 0) { System.out.println(answer.substring(1)); return; } for (int i = n; i >= 1; i--) { c++; partition(n-i, answer + "+" + i); } } public static void main(String[] args) { int n = 5; partition(n,""); System.out.println(c); } }The one with max gave 11 and the without max gave 33.
It may seem clichéd but you can’t optimize time and space at the same time! 🙂
yeah..later found that adding “max” also helps in chucking dupes!! 🙂