Integer Partition in Java

Question

Here is my code to do this. It works for the string representation, but not the ArrayList<ArrayList<Integer>> one.

public static void partition(int n) {
 partition(n, n, "",
 new ArrayList<ArrayList<Integer>>(),
 new ArrayList<Integer>());
}
public static void partition(int n, int max, String temp,
 ArrayList<ArrayList<Integer>> master,
 ArrayList<Integer> holder) {
 if (n == 0) {
 ArrayList<Integer> temp1 = new ArrayList<Integer>();
 for (int i = 0; i <= holder.size(); i++) {
 temp1.add(holder.get(0));
 holder.remove(0);
 }
 master.add(temp1);
 System.out.println(temp);
 }
 for (int i = Math.min(max, n); i >= 1; i--) {
 holder.add(i);
 partition(n - i, i, temp + " " + i, master, holder);
 }
}

The reason that I am doing the funny business with temp1 is that if I were to just add temp to master, the previous elements would change (all elements in master would be references pointing to the same place) so this is my attempt at a deep copy + clear.

The string works. Why doesn't the ArrayList<ArrayList<Integer>>? And how can I fix it?

Output of the ArrayList<ArrayList<Integer>> is:

[[5], [4, 1], [3, 2], [1, 1], [2, 2], [1, 1, 1], [1, 1, 1, 1]]

Answer 1

You are mixing up your holder array inside the if branch which you shouldn't do. Try the following:

public static void partition(int n, int max, String temp,
 ArrayList<ArrayList<Integer>> master,
 ArrayList<Integer> holder) {
 if (n == 0) {
 ArrayList<Integer> temp1 = new ArrayList<Integer>();
 for (int i = 0; i < holder.size(); i++) {
 temp1.add(holder.get(i));
 }
 master.add(temp1);
 System.out.println(temp);
 }
 for (int i = Math.min(max, n); i >= 1; i--) {
 holder.add(i);
 partition(n - i, i, temp + " " + i, master, holder);
 holder.remove(holder.size() - 1);
 }
}

Answer 2

You have to pass a copy of holder to each subsequent branch of the recursion.

Java 7:

public static void main(String[] args) {
 List<List<Integer>> list = partition(5);
 for (List<Integer> comb : list)
 System.out.println(comb);
}

public static List<List<Integer>> partition(int n) {
 List<List<Integer>> list = new ArrayList<>();
 partition(n, n, "", list, new ArrayList<Integer>());
 return list;
}

public static void partition(int i, int max, String indent,
 List<List<Integer>> master, List<Integer> holder) {
 if (i == 0) {
 master.add(holder);
 System.out.println(
 indent + "i=" + i + ",max=" + max + " comb=" + holder);
 }
 for (int j = Math.min(max, i); j >= 1; j--) {
 ArrayList<Integer> temp = new ArrayList<>(holder);
 temp.add(j);
 System.out.println(
 indent + "i=" + i + ",j=" + j + ",max=" + max + " temp=" + temp);
 partition(i - j, j, indent + " ", master, temp);
 }
}

Output of the recursive tree n=5:

i=5,j=5,max=5 temp=[5]
 i=0,max=5 comb=[5]
i=5,j=4,max=5 temp=[4]
 i=1,j=1,max=4 temp=[4, 1]
 i=0,max=1 comb=[4, 1]
i=5,j=3,max=5 temp=[3]
 i=2,j=2,max=3 temp=[3, 2]
 i=0,max=2 comb=[3, 2]
 i=2,j=1,max=3 temp=[3, 1]
 i=1,j=1,max=1 temp=[3, 1, 1]
 i=0,max=1 comb=[3, 1, 1]
i=5,j=2,max=5 temp=[2]
 i=3,j=2,max=2 temp=[2, 2]
 i=1,j=1,max=2 temp=[2, 2, 1]
 i=0,max=1 comb=[2, 2, 1]
 i=3,j=1,max=2 temp=[2, 1]
 i=2,j=1,max=1 temp=[2, 1, 1]
 i=1,j=1,max=1 temp=[2, 1, 1, 1]
 i=0,max=1 comb=[2, 1, 1, 1]
i=5,j=1,max=5 temp=[1]
 i=4,j=1,max=1 temp=[1, 1]
 i=3,j=1,max=1 temp=[1, 1, 1]
 i=2,j=1,max=1 temp=[1, 1, 1, 1]
 i=1,j=1,max=1 temp=[1, 1, 1, 1, 1]
 i=0,max=1 comb=[1, 1, 1, 1, 1]

Output of the list n=5:

[5]
[4, 1]
[3, 2]
[3, 1, 1]
[2, 2, 1]
[2, 1, 1, 1]
[1, 1, 1, 1, 1]

---

^{See also: Building permutation that sums to a number efficiently}