streamalism.org

1. Introduksjon

I denne veiledningen, vi vil diskutere løsningen på k-kombinasjonsproblemet i Java.

Først skal vi diskutere og implementere både rekursive og iterative algoritmer for å generere alle kombinasjoner av en gitt størrelse. Deretter vil vi gjennomgå løsninger ved hjelp av vanlige Java-biblioteker.

2. Kombinasjonsoversikt

For å si det enkelt, en kombinasjon er et delsett av elementer fra et gitt sett.

I motsetning til permutasjoner, spiller ikke rekkefølgen vi velger de enkelte elementene noen rolle. I stedet bryr vi oss bare om et bestemt element er i utvalget.

For eksempel, i et kortspill, må vi dele ut 5 kort ut av pakken som består av 52 kort. Vi har ingen interesse for i hvilken rekkefølge de 5 kortene ble valgt. Snarere bryr vi oss bare om hvilke kort som er til stede i hånden.

Noen problemer krever at vi vurderer alle mulige kombinasjoner. For å gjøre dette oppregner vi de forskjellige kombinasjonene.

Antall forskjellige måter å velge "r" -elementer fra settet med "n" -elementer kan uttrykkes matematisk med følgende formel:

Derfor kan antall måter å velge elementer vokse eksponentielt i verste fall. Derfor, for store populasjoner, er det kanskje ikke mulig å telle opp de forskjellige valgene.

I slike tilfeller kan vi tilfeldig velge noen få representative valg. Prosessen kalles prøvetaking.

Deretter gjennomgår vi de forskjellige algoritmene for å liste kombinasjoner.

3. Rekursive algoritmer for å generere kombinasjoner

Rekursive algoritmer fungerer vanligvis ved å dele et problem i lignende mindre problemer. Denne prosessen fortsetter til vi når den avsluttende tilstanden, som også er basissaken. Så løser vi basissaken direkte.

Vi diskuterer to måter å dele oppgaven med å velge elementer fra et sett. Den første tilnærmingen deler problemet med hensyn til elementene i settet. Den andre tilnærmingen deler problemet ved å spore bare de valgte elementene.

3.1. Partisjonere av elementer i hele settet

La oss dele oppgaven med å velge “r ” elementer fra “n ” gjenstander ved å inspisere elementene en etter en. For hvert element i settet kan vi enten inkludere det i utvalget eller ekskludere det.

Hvis vi inkluderer det første elementet, må vi velge “r – 1″ elementer fra de resterende “n - 1 ″ gjenstander. På den andre siden, hvis vi forkaster det første elementet, må vi velge “r ” elementer ut av de gjenværende “n - 1 ″ gjenstander.

Dette kan matematisk uttrykkes som:

La oss nå se på den rekursive implementeringen av denne tilnærmingen:

privat ugyldig hjelper (Listekombinasjoner, int-data [], int start, int-slutt, int-indeks) {if (index == data.length) {int [] kombinasjon = data.clone (); kombinasjoner. legge til (kombinasjon); } annet hvis (start <= slutt) {data [index] = start; hjelper (kombinasjoner, data, start + 1, slutt, indeks + 1); hjelper (kombinasjoner, data, start + 1, slutt, indeks); }}

De hjelper metoden gjør to rekursive samtaler til seg selv. Den første samtalen inkluderer det nåværende elementet. Den andre samtalen forkaster det nåværende elementet.

Deretter, la oss skrive kombinasjonsgeneratoren ved hjelp av dette hjelper metode:

offentlig Liste generer (int n, int r) {Listekombinasjoner = ny ArrayList (); hjelper (kombinasjoner, ny int [r], 0, n-1, 0); returkombinasjoner; }

I koden ovenfor er generere metoden setter opp den første samtalen til hjelper metode og passerer de riktige parametrene.

La oss kalle denne metoden for å generere kombinasjoner:

Listekombinasjoner = generer (N, R); for (int [] kombinasjon: kombinasjoner) {System.out.println (Arrays.toString (kombinasjon)); } System.out.printf ("genererte% d kombinasjoner av% d elementer fra% d", kombinasjoner.størrelse (), R, N);

Ved gjennomføring av programmet får vi følgende utdata:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] genererte 10 kombinasjoner av 2 elementer fra 5

Til slutt, la oss skrive testsaken:

@Test offentlig ugyldighet givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount () {SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator (); Listevalg = generator.generert (N, R); assertEquals (nCr, selection.size ()); }

Det er lett å observere at den nødvendige stabelstørrelsen er antall elementer i settet. Når antall elementer i settet er stort, for eksempel større enn den maksimale dybden for samtalestakken, vil vi flyte over stakken og få en StackOverflowError.

Derfor fungerer denne tilnærmingen ikke hvis inngangssettet er stort.

3.2. Partisjonere av elementer i kombinasjonen

I stedet for å spore elementene i inngangssettet, vi deler oppgaven ved å spore elementene i utvalget.

La oss først bestille elementene i inngangssettet ved hjelp av indeksene “1” til “n ”. Nå kan vi velge det første elementet fra det første “n-r + 1 ″ gjenstander.

La oss anta at vi valgte kth punkt. Så må vi velge “r - 1 ″ gjenstander fra de resterende “n - k ” varer indeksert “k + 1 til "n ”.

Vi uttrykker denne prosessen matematisk som:

Neste, la oss skrive den rekursive metoden for å implementere denne tilnærmingen:

privat ugyldig hjelper (Listekombinasjoner, int-data [], int start, int-slutt, int-indeks) {if (index == data.length) {int [] kombinasjon = data.clone (); kombinasjoner. legge til (kombinasjon); } annet {int max = Math.min (end, end + 1 - data.length + index); for (int i = start; i <= max; i ++) {data [index] = i; hjelper (kombinasjoner, data, i + 1, slutt, indeks + 1); }}}

I koden ovenfor er til loop velger neste element, deretter, det kaller hjelper() metode rekursivt for å velge gjenværende gjenstander. Vi stopper når ønsket antall artikler er valgt.

La oss deretter bruke hjelper metode for å generere valg:

public List generere (int n, int r) {List kombinasjoner = ny ArrayList (); hjelper (kombinasjoner, ny int [r], 0, n - 1, 0); returkombinasjoner; }

Til slutt, la oss skrive en prøvesak:

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

Størrelsen på anropsstakken som brukes av denne tilnærmingen, er den samme som antall elementer i utvalget. Derfor, denne tilnærmingen kan fungere for store innganger så lenge antall elementer som skal velges er mindre enn maksimal dybde for samtalestakk.

Hvis antall elementer som skal velges også er stort, vil denne metoden ikke fungere.

4. Iterativ algoritme

I den iterative tilnærmingen starter vi med en innledende kombinasjon. Deretter, vi fortsetter å generere neste kombinasjon fra den nåværende til vi har generert alle kombinasjoner.

La oss generere kombinasjonene i leksikografisk rekkefølge. Vi starter med den laveste leksikografiske kombinasjonen.

For å få den neste kombinasjonen fra den nåværende, finner vi den retteste plasseringen i den nåværende kombinasjonen som kan inkrementeres. Deretter øker vi plasseringen og genererer lavest mulig leksikografisk kombinasjon til høyre for stedet.

La oss skrive koden som følger denne tilnærmingen:

public List generere (int n, int r) {List kombinasjoner = ny ArrayList (); int [] kombinasjon = ny int [r]; // initialiser med laveste leksikografiske kombinasjon for (int i = 0; i <r; i ++) {kombinasjon [i] = i; } mens (kombinasjon [r - 1] <n) {kombinasjoner.add (kombinasjon.klon ()); // generere neste kombinasjon i leksikografisk rekkefølge int t = r - 1; mens (t! = 0 && kombinasjon [t] == ​​n - r + t) {t--; } kombinasjon [t] ++; for (int i = t + 1; i <r; i ++) {kombinasjon [i] = kombinasjon [i - 1] + 1; }} returkombinasjoner; }

Deretter, la oss skrive testsaken:

@Test offentlig ugyldighet gittSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount () {IterativeCombinationGenerator generator = new IterativeCombinationGenerator (); Listevalg = generator.generert (N, R); assertEquals (nCr, selection.size ()); }

La oss nå bruke noen Java-biblioteker for å løse problemet.

5. Java-biblioteker som implementerer kombinasjoner

Så langt det er mulig, bør vi gjenbruke eksisterende bibliotekimplementeringer i stedet for å rulle ut våre egne. I denne delen vil vi utforske følgende Java-biblioteker som implementerer kombinasjoner:

• Apache Commons
• Guava
• CombinatoricsLib

5.1. Apache Commons

De CombinatoricsUtils klasse fra Apache Commons gir mange kombinasjonsfunksjoner. Spesielt den kombinasjonerIterator metoden returnerer en iterator som vil generere kombinasjoner i leksikografisk rekkefølge.

La oss først legge til Maven-avhengigheten commons-math3 til prosjektet:

 org.apache.commons commons-math3 3.6.1 

Neste, la oss bruke kombinasjonerIterator metode for å skrive ut kombinasjonene:

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

5.2. Google Guava

De Settene klasse fra Guava bibliotek gir verktøy metoder for sett-relaterte operasjoner. De kombinasjoner metoden returnerer alle delmengder av en gitt størrelse.

La oss først legge til mavenavhengigheten for Guava-biblioteket til prosjektet:

 com.google.guava guava 27.0.1-jre 

Neste, la oss bruke kombinasjoner metode for å generere kombinasjoner:

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

Her bruker vi ImmutableSet.of metode for å lage et sett fra de gitte tallene.

5.3. CombinatoricsLib

CombinatoricsLib er et lite og enkelt Java-bibliotek for permutasjoner, kombinasjoner, delmengder, heltallspartisjoner og kartesisk produkt.

For å bruke den i prosjektet, la oss legge til combinatoricslib3 Maven avhengighet:

 com.github.dpaukov combinatoricslib3 3.3.0 

Neste, la oss bruke biblioteket til å skrive ut kombinasjonene:

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

Dette gir følgende utdata ved utfø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 er tilgjengelige på combinatoricslib3-eksempel.

6. Konklusjon

I denne artikkelen implementerte vi noen få algoritmer for å generere kombinasjoner.

Vi gjennomgikk også noen få implementeringer av biblioteket. Vanligvis bruker vi disse i stedet for å rulle våre egne.

Som vanlig finner du full kildekode på GitHub.