Partitions of a set - Storing results in a series of nested lists

Question

I have code that will list all partitions of a set. The code is from this site: Generating the Partitions of a Set.

Rather than just print the partitions out, I want to store them as lists. I want to model my result after what is returned in this recursive example: How to find all partitions of a set.

I want a list of a list of a list of integers. The inner list is the subset of the partition contained in the middle list, and the outer list is what contains the full set of all partitions.

Here is my code (converted to Java from C, with comments still in place from the original website post):

import java.util.ArrayList;
import java.util.List;


public class PartitionApp {


  public static class PNR {
    static
    /*
     printp
      - print out the partitioning scheme s of n elements 
      as: {1, 2, 4} {3}
    */
    ArrayList < ArrayList < ArrayList < Integer >>> outerList = new ArrayList < > ();
    public static void PNR(int[] s, int n) {
      /* Get the total number of partitions. In the example above, 2.*/

      int part_num = 1;
      int i;

      for (i = 0; i < n; ++i)
        if (s[i] > part_num) {

          part_num = s[i];
        }
        /* Print the p partitions. */

      int p;

      for (p = part_num; p >= 1; --p) {

        System.out.print("{");
        ArrayList < Integer > innerList = new ArrayList < > ();
        ArrayList < ArrayList < Integer >> middleList = new ArrayList < > ();
        /* If s[i] == p, then i + 1 is part of the pth partition. */
        for (i = 0; i < n; ++i) {
          if (s[i] == p) {
            innerList.add(i + 1);
            System.out.print(i + 1);
            System.out.print(",");
          }

        }
        middleList.add(innerList);
        outerList.add(middleList);

        System.out.print("} ");
      }

      System.out.print("\n");
      System.out.println(outerList);

    }

    /*
 next
  - given the partitioning scheme represented by s and m, generate
  the next

 Returns: 1, if a valid partitioning was found
  0, otherwise
*/
    static int next(int[] s, int[] m, int n) {
      /* Update s: 1 1 1 1 -> 2 1 1 1 -> 1 2 1 1 -> 2 2 1 1 -> 3 2 1 1 ->
 1 1 2 1 ... */
      /*int j;
 printf(" -> (");
 for (j = 0; j < n; ++j)
  printf("%d, ", s[j]);
 printf("\b\b)\n");*/
      int i = 0;
      ++s[i];
      while ((i < n - 1) && (s[i] > m[i + 1] + 1)) {
        s[i] = 1;
        ++i;
        ++s[i];
      }

      /* If i is has reached n-1 th element, then the last unique partitiong
 has been found*/
      if (i == n - 1)
        return 0;

      /* Because all the first i elements are now 1, s[i] (i + 1 th element)
 is the largest. So we update max by copying it to all the first i
 positions in m.*/
      if (s[i] > m[i])
        m[i] = s[i];
      for (int j = i - 1; j >= 0; --j) {
        m[j] = m[i];

      }


      /* for (i = 0; i < n; ++i)
        printf("%d ", m[i]);
       getchar();*/
      return 1;
    }

    public static void main(String[] args) {
      int count = 0;
      int[] s = new int[16];
      /* s[i] is the number of the set in which the ith element
         should go */
      int[] m = new int[16]; /* m[i] is the largest of the first i elements in s*/

      int n = 4;
      int i;
      /* The first way to partition a set is to put all the elements in the same
    subset. */
      for (i = 0; i < n; ++i) {
        s[i] = 1;
        m[i] = 1;
      }

      /* Print the first partitioning. */
      PNR(s, n);

      /* Print the other partitioning schemes. */
      while (next(s, m, n) != 0) {
        PNR(s, n);
        count++;
      }
      count = count + 1;
      System.out.println("count = " + count);


      // return 0;
    }

  }

}

The result I get for n=4 looks like this (square brackets replaced by curly brackets for formatting purposes):

{{{1, 2, 3, 4}}, {{1}}, {{2, 3, 4}}, {{2}}, {{1, 3, 4}}, {{1, 2}}, {{3, 4}}.....

There is no "middle" grouping. All inner subsets (which should be part of a group of n elements) are contained as lists in the outer set. I'm not setting up the inner, middle, and outer lists correctly and have been struggling with this for a day. I'm hoping that someone can help me see my error.

Thank you, Rebecca

Answer 1

Took me a while but I found a solution! What I do is I take all possible parts out of the array and then recurse on what is left over, then add the part that I took out as a part of the partitions returned in the recursion. This then goes into one big array which contains all possible partitions. To force a certain ordering I make it so that this part we take out always takes the first element. This way you won't get results like [[1], [2, 3]] and [[2, 3], [1]] which are basically just the same partition.

public static int[][][] getAllPartitions(int[] array) throws Exception {
    int[][][] res = new int[0][][];
    int n = 1;
    for (int i = 0; i < array.length; i++) {
        n *= 2;
    }
    for (int i = 1; i < n; i += 2) {
        boolean[] contains = new boolean[array.length];
        int length = 0;
        int k = i;
        for (int j = 0; j < array.length; j++) {
            contains[j] = k % 2 == 1;
            length += k % 2;
            k /= 2;
        }
        int[] firstPart = new int[length];
        int[] secondPart = new int[array.length - length];
        int p = 0;
        int q = 0;
        for (int j = 0; j < array.length; j++) {
            if (contains[j]) {
                firstPart[p++] = array[j];
            } else {
                secondPart[q++] = array[j];
            }
        }
        int[][][] partitions;
        if (length == array.length) {
            partitions = new int[][][] {{firstPart}};
        } else {
            partitions = getAllPartitions(secondPart);
            for (int j = 0; j < partitions.length; j++) {
                int[][] partition = new int[partitions[j].length + 1][];
                partition[0] = firstPart;
                System.arraycopy(partitions[j], 0, partition, 1, partitions[j].length);
                partitions[j] = partition;
            }
        }
        int[][][] newRes = new int[res.length + partitions.length][][];
        System.arraycopy(res, 0, newRes, 0, res.length);
        System.arraycopy(partitions, 0, newRes, res.length, partitions.length);
        res = newRes;
    }
    return res;
}