Generieren Sie Kombinationen in Java

1. Einleitung

In diesem Tutorial werden wir die Lösung des Problems der k-Kombinationen in Java diskutieren .

Zunächst werden sowohl rekursive als auch iterative Algorithmen diskutiert und implementiert, um alle Kombinationen einer bestimmten Größe zu generieren. Anschließend überprüfen wir Lösungen mit gängigen Java-Bibliotheken.

2. Kombinationsübersicht

Einfach ausgedrückt ist eine Kombination eine Teilmenge von Elementen aus einer bestimmten Menge .

Im Gegensatz zu Permutationen spielt die Reihenfolge, in der wir die einzelnen Elemente auswählen, keine Rolle. Stattdessen ist es uns nur wichtig, ob ein bestimmtes Element in der Auswahl enthalten ist.

Zum Beispiel müssen wir in einem Kartenspiel 5 Karten aus dem Paket aus 52 Karten austeilen. Wir haben kein Interesse an der Reihenfolge, in der die 5 Karten ausgewählt wurden. Vielmehr ist es uns egal, welche Karten in der Hand vorhanden sind.

Bei einigen Problemen müssen wir alle möglichen Kombinationen bewerten. Dazu zählen wir die verschiedenen Kombinationen auf.

Die Anzahl der verschiedenen Möglichkeiten, „r“ -Elemente aus der Menge der „n“ -Elemente auszuwählen, kann mit der folgenden Formel mathematisch ausgedrückt werden:

Daher kann die Anzahl der Möglichkeiten zur Auswahl von Elementen im schlimmsten Fall exponentiell zunehmen. Daher ist es für große Populationen möglicherweise nicht möglich, die verschiedenen Auswahlen aufzuzählen.

In solchen Fällen können wir zufällig einige repräsentative Auswahlen auswählen. Der Prozess wird als Abtastung bezeichnet .

Als nächstes werden wir die verschiedenen Algorithmen überprüfen, um Kombinationen aufzulisten.

3. Rekursive Algorithmen zur Erzeugung von Kombinationen

Rekursive Algorithmen arbeiten normalerweise, indem sie ein Problem in ähnliche kleinere Probleme aufteilen. Dieser Prozess wird fortgesetzt, bis wir die Endbedingung erreicht haben, die auch der Basisfall ist. Dann lösen wir den Basisfall direkt.

Wir werden zwei Möglichkeiten diskutieren, um die Aufgabe der Auswahl von Elementen aus einer Menge zu unterteilen. Der erste Ansatz unterteilt das Problem in die Elemente in der Menge. Der zweite Ansatz unterteilt das Problem, indem nur die ausgewählten Elemente verfolgt werden.

3.1. Partitionierung nach Elementen im gesamten Satz

Teilen wir die Aufgabe der Auswahl von " r" -Elementen aus " n" Elementen, indem wir die Elemente einzeln untersuchen. Für jedes Element im Set können wir es entweder in die Auswahl aufnehmen oder ausschließen.

Wenn wir das erste Element enthalten, dann müssen wir wählen „r - 1" Elemente aus dem verbleibenden „ n - 1" Artikel . Auf der anderen Seite, wenn wir das erste Element verwerfen, dann brauchen wir , um „ r“ Elemente aus dem verbleibenden „ n - 1" Artikel.

Dies kann mathematisch ausgedrückt werden als:

Betrachten wir nun die rekursive Implementierung dieses Ansatzes:

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else if (start <= end) { data[index] = start; helper(combinations, data, start + 1, end, index + 1); helper(combinations, data, start + 1, end, index); } }

Die Hilfsmethode führt zwei rekursive Aufrufe an sich selbst durch. Der erste Aufruf enthält das aktuelle Element. Der zweite Aufruf verwirft das aktuelle Element.

Als nächstes schreiben wir den Kombinationsgenerator mit dieser Hilfsmethode :

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n-1, 0); return combinations; }

Im obigen Code richtet die Methode generate den ersten Aufruf der Hilfsmethode ein und übergibt die entsprechenden Parameter.

Rufen Sie als Nächstes diese Methode auf, um Kombinationen zu generieren:

List combinations = generate(N, R); for (int[] combination : combinations) { System.out.println(Arrays.toString(combination)); } System.out.printf("generated %d combinations of %d items from %d ", combinations.size(), R, N);

Beim Ausführen des Programms erhalten wir folgende Ausgabe:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] generated 10 combinations of 2 items from 5

Zum Schluss schreiben wir den Testfall:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount() { SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Es ist leicht zu beobachten, dass die erforderliche Stapelgröße die Anzahl der Elemente in der Menge ist. Wenn die Anzahl der Elemente in der Gruppe beispielsweise größer als die maximale Aufrufstapeltiefe ist, wird der Stapel überlaufen und ein StackOverflowError angezeigt .

Daher funktioniert dieser Ansatz nicht, wenn der Eingabesatz groß ist.

3.2. Partitionierung nach Elementen in der Kombination

Anstatt die Elemente im Eingabesatz zu verfolgen, teilen wir die Aufgabe auf, indem wir die Elemente in der Auswahl verfolgen .

Ordnen wir zunächst die Elemente im Eingabesatz mit den Indizes „1“ bis „ n“ . Jetzt können wir den ersten Artikel aus den ersten " n-r + 1" -Elementen auswählen .

Nehmen wir an, wir haben den k-ten Punkt gewählt. Dann müssen wir " r - 1" Elemente aus den verbleibenden " n - k" Elementen auswählen , die mit " k + 1" bis " n" indiziert sind .

Wir drücken diesen Prozess mathematisch aus als:

Als nächstes schreiben wir die rekursive Methode, um diesen Ansatz zu implementieren:

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else { int max = Math.min(end, end + 1 - data.length + index); for (int i = start; i <= max; i++) { data[index] = i; helper(combinations, data, i + 1, end, index + 1); } } }

Im obigen Code wählt die for- Schleife das nächste Element aus. Anschließend ruft sie die helper () -Methode rekursiv auf, um die verbleibenden Elemente auszuwählen . Wir hören auf, wenn die gewünschte Anzahl von Elementen ausgewählt wurde.

Verwenden Sie als Nächstes die Hilfsmethode , um eine Auswahl zu generieren:

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n - 1, 0); return combinations; }

Zum Schluss schreiben wir einen Testfall:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount() { SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Die von diesem Ansatz verwendete Aufrufstapelgröße entspricht der Anzahl der Elemente in der Auswahl. Daher kann dieser Ansatz für große Eingaben funktionieren, solange die Anzahl der auszuwählenden Elemente geringer ist als die maximale Tiefe des Aufrufstapels.

Wenn die Anzahl der auszuwählenden Elemente ebenfalls groß ist, funktioniert diese Methode nicht.

4. Iterativer Algorithmus

Beim iterativen Ansatz beginnen wir mit einer anfänglichen Kombination. Dann generieren wir die nächste Kombination aus der aktuellen, bis wir alle Kombinationen generiert haben .

Lassen Sie uns die Kombinationen in lexikografischer Reihenfolge generieren. Wir beginnen mit der niedrigsten lexikografischen Kombination.

Um die nächste Kombination aus der aktuellen zu erhalten, finden wir die Position ganz rechts in der aktuellen Kombination, die erhöht werden kann. Dann erhöhen wir den Ort und generieren die niedrigstmögliche lexikografische Kombination rechts von diesem Ort.

Schreiben wir den Code, der diesem Ansatz folgt:

public List generate(int n, int r) { List combinations = new ArrayList(); int[] combination = new int[r]; // initialize with lowest lexicographic combination for (int i = 0; i < r; i++) { combination[i] = i; } while (combination[r - 1] < n) { combinations.add(combination.clone()); // generate next combination in lexicographic order int t = r - 1; while (t != 0 && combination[t] == n - r + t) { t--; } combination[t]++; for (int i = t + 1; i < r; i++) { combination[i] = combination[i - 1] + 1; } } return combinations; }

Als nächstes schreiben wir den Testfall:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount() { IterativeCombinationGenerator generator = new IterativeCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Lassen Sie uns nun einige Java-Bibliotheken verwenden, um das Problem zu lösen.

5. Java-Bibliotheken, die Kombinationen implementieren

So weit wie möglich sollten wir vorhandene Bibliotheksimplementierungen wiederverwenden, anstatt unsere eigenen einzuführen. In diesem Abschnitt werden die folgenden Java-Bibliotheken untersucht, die Kombinationen implementieren:

  • Apache Commons
  • Guave
  • CombinatoricsLib

5.1. Apache Commons

The CombinatoricsUtils class from Apache Commons provides many combination utility functions. In particular, the combinationsIterator method returns an iterator that will generate combinations in lexicographic order.

First, let's add the Maven dependency commons-math3 to the project:

 org.apache.commons commons-math3 3.6.1 

Next, let's use the combinationsIterator method to print the combinations:

public static void generate(int n, int r) { Iterator iterator = CombinatoricsUtils.combinationsIterator(n, r); while (iterator.hasNext()) { final int[] combination = iterator.next(); System.out.println(Arrays.toString(combination)); } }

5.2. Google Guava

The Sets class from Guava library provides utility methods for set-related operations. The combinations method returns all subsets of a given size.

First, let's add the maven dependency for the Guava library to the project:

 com.google.guava guava 27.0.1-jre 

Next, let's use the combinations method to generate combinations:

Set
    
      combinations = Sets.combinations(ImmutableSet.of(0, 1, 2, 3, 4, 5), 3);
    

Here, we are using the ImmutableSet.of method to create a set from the given numbers.

5.3. CombinatoricsLib

CombinatoricsLib is a small and simple Java library for permutations, combinations, subsets, integer partitions, and cartesian product.

To use it in the project, let's add the combinatoricslib3 Maven dependency:

 com.github.dpaukov combinatoricslib3 3.3.0 

Next, let's use the library to print the combinations:

Generator.combination(0, 1, 2, 3, 4, 5) .simple(3) .stream() .forEach(System.out::println);

This produces the following output on execution:

[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 3, 4] [0, 3, 5] [0, 4, 5] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5]

More examples are available at combinatoricslib3-example.

6. Conclusion

In this article, we implemented a few algorithms to generate combinations.

Wir haben auch einige Bibliotheksimplementierungen überprüft. Normalerweise verwenden wir diese, anstatt unsere eigenen zu rollen.

Wie immer finden Sie den vollständigen Quellcode auf GitHub.