Aufzählung aller k-Teilungen von 1d Array mit N Elementen?

Question

Dies scheint eine einfache Anfrage zu sein, aber Google ist nicht mein Freund, denn "Partition" führt zu einer Vielzahl von Treffern im Bereich Datenbank und Dateisystem.

Ich muss alle Partitionen eines Arrays mit N Werten (N ist konstant) in k Unterarrays aufzählen. Die Unterfelder sind genau das - ein Startindex und ein Endindex. Die Gesamtreihenfolge des ursprünglichen Arrays wird beibehalten.

Zum Beispiel mit N=4 und k=2:

[ | a b c d ] (0, 4)
[ a | b c d ] (1, 3)
[ a b | c d ] (2, 2)
[ a b c | d ] (3, 1)
[ a b c d | ] (4, 0)

Und mit k=3:

[ | | a b c d ] (0, 0, 4)
[ | a | b c d ] (0, 1, 3)
  :
[ a | b | c d ] (1, 1, 2)
[ a | b c | d ] (1, 2, 1)
  :
[ a b c d | | ] (4, 0, 0)

Ich bin mir ziemlich sicher, dass dies kein originelles Problem ist (und nein, es ist keine Hausaufgabe), aber ich würde es gerne für jedes k <= N machen, und es wäre großartig, wenn die späteren Durchläufe (wenn k wächst) von früheren Ergebnissen profitieren würden.

Wenn Sie einen Link haben, teilen Sie ihn bitte mit.

Answer 1

Zur Wiederverwendung der früheren Ergebnisse (für geringere Werte von k ), können Sie eine Rekursion durchführen.

Stellen Sie sich eine solche Partitionierung als eine Liste von Endindizes vor (der Startindex für eine beliebige Partition ist einfach der Endindex der letzten Partition oder 0 für die erste Partition).

Ihr Satz von Partitionierungen ist also einfach ein Satz aller Arrays von k nicht abnehmende ganze Zahlen zwischen 0 und N.

Si k begrenzt ist, können Sie dies über k geschachtelte Schleifen

for (i[0]=0; i[0] < N; i[0]++) {
    for (i[1]=i[0]; i[1] < N; i[1]++) {
    ...
            for (i[10]=i[9]; i[10] < N; i[10]++) {
                push i[0]==>i[10] onto the list of partitionings.
            }
    ...
    }
}

Si k unbegrenzt ist, können Sie dies rekursiv tun.

Eine Reihe von k Partitionen zwischen den Indizes S und E erhält man durch:

• Schleifenbildung für das "Ende der ersten Partition" EFP zwischen S und E. Für jeden Wert:

  • Rekursive Suche nach einer Liste von k-1 Teilungen zwischen MAB und S

  • Für jeden Vektor in dieser Liste wird "EFP" an diesen Vektor angehängt.

  • resultierender Vektor der Länge k wird der Ergebnisliste hinzugefügt.

Bitte beachten Sie, dass meine Antwort Listen mit den Endpunkten jedes Slice erzeugt. Wenn Sie (wie Ihr Beispiel zeigt) eine Liste der LÄNGEN jedes Slice wünschen, müssen Sie die Längen durch Subtraktion des letzten Slice-Endes vom aktuellen Slice-Ende ermitteln.

Answer 2

Jede Partition kann durch die k-1 Indizes beschrieben werden, die die Teile trennen. Da die Ordnung erhalten bleibt, müssen diese Indizes nicht abnehmend sein. Das heißt, es gibt eine direkte Entsprechung zwischen Teilmengen der Größe k-1 und den gesuchten Partitionen.

Um über alle Teilmengen der Größe k-1 zu iterieren, können Sie die Frage überprüfen:

Wie generiert man iterativ k Elemente aus einer Menge der Größe n in Java?

Die einzige Schwierigkeit besteht darin, dass, wenn leere Teile erlaubt sind, mehrere Schnittpunkte zusammenfallen können, aber eine Teilmenge kann jeden Index höchstens einmal enthalten. Sie müssen den Algorithmus leicht anpassen, indem Sie ihn ersetzen:

        processLargerSubsets(set, subset, subsetSize + 1, j + 1);

von

        processLargerSubsets(set, subset, subsetSize + 1, j);