セットのパーティション - 結果を一連のネストされたリストに格納する

Question

私は、セットのすべてのパーティションをリストするコードを持っています。このコードはGenerating the Partitions of a Setからのものです。

パーティションを印刷するだけでなく、それらをリストとして保存します。私はこの再帰的な例で返されるものの後に結果をモデル化したい：How to find all partitions of a set。

整数のリストのリストが必要です。内側のリストはミドルリストに含まれるパーティションのサブセットであり、外側のリストはすべてのパーティションの完全なセットを含むものです。ここで

は私のコードは、（元のウェブサイトのポストから、まだ場所でのコメントで、CからJavaへの変換）です：

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

 

 
public class PartitionApp { 
 

 

 
    public static class PNR { 
 
    static 
 
    /* 
 
    \t printp 
 
    \t \t - print out the partitioning scheme s of n elements 
 
    \t \t 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); 
 

 
    } 
 

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

 
\t Returns: 1, if a valid partitioning was found 
 
\t \t 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 -> 
 
\t 1 1 2 1 ... */ 
 
     /*int j; 
 
\t printf(" -> ("); 
 
\t for (j = 0; j < n; ++j) 
 
\t \t printf("%d, ", s[j]); 
 
\t 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 
 
\t has been found*/ 
 
     if (i == n - 1) 
 
     return 0; 
 

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

 
     } 
 

 

 
     /* \t for (i = 0; i < n; ++i) 
 
     \t \t printf("%d ", m[i]); 
 
     \t 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 
 
     \t \t \t 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 
 
\t 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); 
 

 

 
     // \t return 0; 
 
    } 
 

 
    } 
 

 
}

私が取得n = 4の結果がどのように見えます

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

「中」のグループはありません。すべての内部サブセット（n個の要素のグループの一部でなければならない）は、アウターセットのリストとして含まれます。私は内側、中間、外側のリストを正しく設定しておらず、これと一日苦労しています。私は誰かが私のエラーを見るのを助けることを望んでいる。

ありがとう、 レベッカ

Answer 1

は私にしばらく時間がかかったが、私は解決策を見つけました！私がやることは、配列からすべての可能な部分を取り出し、残っているものを再帰し、再帰で返されたパーティションの一部として取り出した部分を追加することです。次に、すべての可能なパーティションを含む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; 
}