集合的分区 - 将结果存储在一系列嵌套列表中

Question

我有可以列出集合的所有分区的代码。代码来自此站点：Generating the Partitions of a Set.

我不想将分区打印出来，而是将它们存储为列表。我想在这个递归示例返回的内容之后对我的结果进行建模：How to find all partitions of a set.

我想要一个整数列表的列表。内部列表是中间列表中包含的分区的子集，外部列表是包含所有分区的完整集合。

这是我的代码（从 C 转换为 Java，原始网站 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;
    }

  }

}

我得到的 n=4 的结果如下所示（出于格式化目的，方括号被大括号替换）：

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

没有 "middle" 分组。所有内部子集（应该是一组 n 个元素的一部分）都作为列表包含在外部集合中。我没有正确设置内部、中间和外部列表，并且为此苦苦挣扎了一天。我希望有人能帮我看看我的错误。

谢谢，丽贝卡

Answer 1

花了我一段时间，但我找到了解决方案！我所做的是从数组中取出所有可能的部分，然后递归剩下的部分，然后将我取出的部分添加为递归返回的分区的一部分。然后这进入一个包含所有可能分区的大数组。为了强制执行某种排序，我做了这样我们取出的这部分总是采用第一个元素。这样你就不会得到像 [[1], [2, 3]] 和 [[2, 3], [1]] 这样的结果，它们基本上只是同一个分区。

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;
}

集合的分区 - 将结果存储在一系列嵌套列表中

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

java

set

combinatorics

partition