streamalism.org

1. Introduktion

I denne vejledning vi diskuterer løsningen på k-kombinationer-problemet i Java.

Først diskuterer og implementerer vi både rekursive og iterative algoritmer for at generere alle kombinationer af en given størrelse. Derefter gennemgår vi løsninger ved hjælp af almindelige Java-biblioteker.

2. Kombinationsoversigt

Kort fortalt, en kombination er en delmængde af elementer fra et givet sæt.

I modsætning til permutationer betyder den rækkefølge, som vi vælger de enkelte elementer, ikke noget. I stedet er vi kun interesserede i, om et bestemt element er i markeringen.

For eksempel skal vi i et kortspil uddele 5 kort ud af pakken bestående af 52 kort. Vi har ingen interesse i rækkefølgen, hvor de 5 kort blev valgt. Snarere er vi kun interesserede i hvilke kort der er i hånden.

Nogle problemer kræver, at vi evaluerer alle mulige kombinationer. For at gøre dette opregner vi de forskellige kombinationer.

Antallet af forskellige måder at vælge "r" -elementer fra sættet med "n" -elementer kan udtrykkes matematisk med følgende formel:

Derfor kan antallet af måder at vælge elementer vokse eksponentielt i værste fald. Derfor er det muligvis ikke muligt for store befolkninger at tælle de forskellige valg.

I sådanne tilfælde kan vi tilfældigt vælge et par repræsentative valg. Processen kaldes prøveudtagning.

Dernæst gennemgår vi de forskellige algoritmer for at liste kombinationer.

3. Rekursive algoritmer til generering af kombinationer

Rekursive algoritmer fungerer normalt ved at opdele et problem i lignende mindre problemer. Denne proces fortsætter, indtil vi når den afsluttende tilstand, som også er basissagen. Så løser vi basissagen direkte.

Vi diskuterer to måder at underopdele opgaven med at vælge elementer fra et sæt. Den første tilgang opdeler problemet med hensyn til elementerne i sættet. Den anden tilgang opdeler problemet ved kun at spore de valgte elementer.

3.1. Partitionering efter elementer i hele sættet

Lad os opdele opgaven med at vælge “r ” elementer fra “n ” genstande ved at inspicere varerne en efter en. For hvert element i sættet kan vi enten medtage det i markeringen eller ekskludere det.

Hvis vi inkluderer det første element, skal vi vælge “r – 1″ elementer fra de resterende “n - 1 ″ genstande. På den anden side, hvis vi kasserer det første emne, skal vi vælge “r ” elementer ud af de resterende “n - 1 ″ genstande.

Dette kan matematisk udtrykkes som:

Lad os nu se på den rekursive implementering af denne tilgang:

privat ugyldig hjælper (Listekombinationer, int-data [], int-start, int-end, int-indeks) {if (index == data.length) {int [] kombination = data.clone (); kombinationer. tilføj (kombination); } ellers hvis (start <= slut) {data [index] = start; hjælper (kombinationer, data, start + 1, slut, indeks + 1); hjælper (kombinationer, data, start + 1, slut, indeks); }}

Det hjælper metoden foretager to rekursive opkald til sig selv. Det første opkald inkluderer det aktuelle element. Det andet opkald kasserer det aktuelle element.

Lad os derefter skrive kombinationsgeneratoren ved hjælp af dette hjælper metode:

offentlig liste genererer (int n, int r) {Listekombinationer = ny ArrayList (); hjælper (kombinationer, ny int [r], 0, n-1, 0); returkombinationer; }

I ovenstående kode er frembringe metoden opretter det første opkald til hjælper metode og overfører de relevante parametre.

Lad os derefter kalde denne metode for at generere kombinationer:

Listekombinationer = genererer (N, R); for (int [] kombination: kombinationer) {System.out.println (Arrays.toString (kombination)); } System.out.printf ("genererede% d kombinationer af% d elementer fra% d", kombinationer.størrelse (), R, N);

Ved udførelse af programmet får vi følgende output:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] genererede 10 kombinationer af 2 genstande fra 5

Lad os endelig skrive test case:

@Test offentlig ugyldighed givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount () {SetRecursiveCombinationGenerator generator = ny SetRecursiveCombinationGenerator (); Listevalg = generator.genereret (N, R); assertEquals (nCr, selection.size ()); }

Det er let at observere, at den krævede stakstørrelse er antallet af elementer i sættet. Når antallet af elementer i sættet er stort, for eksempel større end den maksimale dybde for opkaldsstakken, overløber vi stakken og får en StackOverflowError.

Derfor fungerer denne tilgang ikke, hvis indgangssættet er stort.

3.2. Partitionering efter elementer i kombinationen

I stedet for at spore elementerne i indgangssættet, vi deler opgaven ved at spore emnerne i markeringen.

Lad os først bestille varerne i indgangssættet ved hjælp af indekserne "1" til "n ”. Nu kan vi vælge det første element fra det første “n-r + 1 ″ genstande.

Lad os antage, at vi valgte kth vare. Derefter skal vi vælge “r - 1 ″ varer fra de resterende “n - k ” varer indekseret “k + 1 ″ til "n ”.

Vi udtrykker denne proces matematisk som:

Næste, lad os skrive den rekursive metode til at implementere denne tilgang:

privat ugyldig hjælper (Listekombinationer, int-data [], int-start, int-end, int-indeks) {if (index == data.length) {int [] kombination = data.clone (); kombinationer. tilføj (kombination); } andet {int max = Math.min (end, end + 1 - data.length + index); for (int i = start; i <= max; i ++) {data [index] = i; hjælper (kombinationer, data, i + 1, slut, indeks + 1); }}}

I ovenstående kode er til loop vælger det næste element, derefter, det kalder det hjælper() metode rekursivt for at vælge de resterende emner. Vi stopper, når det krævede antal varer er valgt.

Lad os derefter bruge hjælper metode til at generere valg:

offentlig liste genererer (int n, int r) {Listekombinationer = ny ArrayList (); hjælper (kombinationer, ny int [r], 0, n - 1, 0); returkombinationer }

Lad os endelig skrive en test case:

@Test offentlig ugyldighed givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount () {SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator (); Listevalg = generator.genereret (N, R); assertEquals (nCr, selection.size ()); }

Opkaldsstakstørrelsen, der anvendes ved denne tilgang, er den samme som antallet af elementer i markeringen. Derfor, denne tilgang kan fungere for store indgange, så længe antallet af elementer, der skal vælges, er mindre end den maksimale dybde på opkaldsstakken.

Hvis antallet af elementer, der skal vælges, også er stort, fungerer denne metode ikke.

4. Iterativ algoritme

I den iterative tilgang starter vi med en indledende kombination. Derefter, vi fortsætter med at generere den næste kombination fra den nuværende, indtil vi har genereret alle kombinationer.

Lad os generere kombinationerne i leksikografisk rækkefølge. Vi starter med den laveste leksikografiske kombination.

For at få den næste kombination fra den aktuelle, finder vi den placering, der er længst til højre i den aktuelle kombination, der kan øges. Derefter øges vi placeringen og genererer den lavest mulige leksikografiske kombination til højre for denne placering.

Lad os skrive koden, der følger denne tilgang:

offentlig liste genererer (int n, int r) {Listekombinationer = ny ArrayList (); int [] kombination = ny int [r]; // initialiser med den laveste leksikografiske kombination for (int i = 0; i <r; i ++) {kombination [i] = i; } mens (kombination [r - 1] <n) {kombinationer.add (kombination.klon ()); // generere næste kombination i leksikografisk rækkefølge int t = r - 1; mens (t! = 0 && kombination [t] == ​​n - r + t) {t--; } kombination [t] ++; for (int i = t + 1; i <r; i ++) {kombination [i] = kombination [i - 1] + 1; }} returkombinationer; }

Lad os derefter skrive testsagen:

@Test offentlig ugyldighed givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount () {IterativeCombinationGenerator generator = ny IterativeCombinationGenerator (); Listevalg = generator.genereret (N, R); assertEquals (nCr, selection.size ()); }

Lad os nu bruge nogle Java-biblioteker til at løse problemet.

5. Java-biblioteker, der implementerer kombinationer

Så vidt muligt bør vi genbruge eksisterende biblioteksimplementeringer i stedet for at udrulle vores egne. I dette afsnit udforsker vi følgende Java-biblioteker, der implementerer kombinationer:

• Apache Commons
• Guava
• CombinatoricsLib

5.1. Apache Commons

Det CombinatoricsUtils klasse fra Apache Commons giver mange kombinationsværktøjsfunktioner. Især den kombinationer Interator metode returnerer en iterator, der genererer kombinationer i leksikografisk rækkefølge.

Lad os først tilføje Maven-afhængighed commons-math3 til projektet:

 org.apache.commons commons-math3 3.6.1 

Næste, lad os bruge kombinationer Interator metode til at udskrive kombinationerne:

offentlig statisk tomrum genererer (int n, int r) {Iterator iterator = CombinatoricsUtils.combinationsIterator (n, r); mens (iterator.hasNext ()) {final int [] kombination = iterator.next (); System.out.println (Arrays.toString (kombination)); }}

5.2. Google Guava

Det Sæt klasse fra Guava-biblioteket giver hjælpemetoder til sætrelaterede operationer. Det kombinationer metoden returnerer alle delmængder af en given størrelse.

Lad os først tilføje maven-afhængigheden af ​​Guava-biblioteket til projektet:

 com.google.guava guava 27.0.1-jre 

Næste, lad os bruge kombinationer metode til at generere kombinationer:

Sæt kombinationer = Sets.combinations (ImmutableSet.of (0, 1, 2, 3, 4, 5), 3);

Her bruger vi ImmutableSet.of metode til at oprette et sæt ud fra de givne tal.

5.3. CombinatoricsLib

CombinatoricsLib er et lille og simpelt Java-bibliotek til permutationer, kombinationer, delmængder, heltalspartitioner og kartesisk produkt.

For at bruge det i projektet, lad os tilføje combinatoricslib3 Maven afhængighed:

 com.github.dpaukov combinatoricslib3 3.3.0 

Næste, lad os bruge biblioteket til at udskrive kombinationerne:

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

Dette producerer følgende output ved udførelse:

[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]

Flere eksempler findes på combinatoricslib3-eksempel.

6. Konklusion

I denne artikel implementerede vi et par algoritmer til at generere kombinationer.

Vi gennemgik også nogle få biblioteksimplementeringer. Typisk bruger vi disse i stedet for at rulle vores egne.

Som sædvanlig kan den fulde kildekode findes på GitHub.