Partitionen eines Satzes - Speichern von Ergebnissen in einer Reihe von verschachtelten Listen

Question

Ich habe Code, der alle Partitionen eines Satzes auflisten wird. Der Code stammt von dieser Site: Generating the Partitions of a Set.

Anstatt nur die Partitionen auszudrucken, möchte ich sie als Listen speichern. Ich möchte mein Ergebnis nach dem modellieren, was in diesem rekursiven Beispiel zurückgegeben wird: How to find all partitions of a set.

Ich möchte eine Liste einer Liste einer Liste von ganzen Zahlen. Die innere Liste ist die Teilmenge der Partition, die in der mittleren Liste enthalten ist, und die äußere Liste enthält den vollständigen Satz aller Partitionen.

Hier ist mein Code (umgerechnet auf Java von C, mit Kommentaren noch an seinem Platz von der ursprünglichen Website post):

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

 
    } 
 

 
}

Das Ergebnis, das ich für n erhalten = 4 sieht aus wie Dies (eckige Klammern werden für Formatierungszwecke durch geschweifte Klammern ersetzt):

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

Es gibt keine "mittlere" Gruppierung. Alle inneren Teilmengen (die Teil einer Gruppe von n Elementen sein sollten) sind als Listen in der äußeren Menge enthalten. Ich ordne die innere, mittlere und äußere Liste nicht richtig auf und kämpfe seit einem Tag damit. Ich hoffe, dass mir jemand helfen kann, meinen Fehler zu sehen.

Danke, Rebecca

Answer 1

dauerte eine Weile, aber ich fand eine Lösung! Was ich mache, ist, dass ich alle möglichen Teile aus dem Array nehme und dann auf das zurückgebe was ich übrig habe, dann füge den Teil hinzu, den ich als Teil der in der Rekursion zurückgegebenen Partitionen herausgenommen habe. Dies geht dann in ein großes Array, das alle möglichen Partitionen enthält. Um eine bestimmte Reihenfolge zu erzwingen, mache ich es so, dass dieser Teil, den wir herausnehmen, immer das erste Element nimmt. Auf diese Weise erhalten Sie keine Ergebnisse wie [[1], [2, 3]] und [[2, 3], [1]], die im Grunde genommen die gleiche Partition sind.

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