Oversikt over kombinasjonsproblemer i Java

1. Oversikt

I denne opplæringen lærer vi hvordan vi kan løse noen vanlige kombinatoriske problemer. De er mest sannsynlig ikke veldig nyttige i en hverdagsjobb; de er imidlertid interessante fra det algoritmiske perspektivet. Vi kan finne dem nyttige for testformål.

Husk at det er mange forskjellige tilnærminger for å løse disse problemene. Vi har prøvd å gjøre løsningene som presenteres enkle å forstå.

2. Genererer permutasjoner

Først, la oss starte med permutasjoner. En permutasjon er en handling for å omorganisere en sekvens på en slik måte at den har en annen rekkefølge.

Som vi vet fra matematikk, for en sekvens av n elementer, det er n! forskjellige permutasjoner. n! er kjent som en faktoriell operasjon:

n! = 1 * 2 * ... * n

Så for eksempel for en sekvens [1, 2, 3] det er seks permutasjoner:

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Faktor vokser veldig raskt - for en sekvens på 10 elementer har vi 3,628,800 forskjellige permutasjoner! I dette tilfellet, vi snakker om permuterende sekvenser, der hvert enkelt element er forskjellig.

2.1. Algoritme

Det er en god ide å tenke på å generere permutasjoner på en rekursiv måte. La oss introdusere ideen om staten. Den vil bestå av to ting: den nåværende permutasjonen og indeksen for det nå behandlede elementet.

Det eneste arbeidet å gjøre i en slik tilstand er å bytte elementet med hver gjenværende og utføre en overgang til en tilstand med den modifiserte sekvensen og indeksen økt med en.

La oss illustrere med et eksempel.

Vi ønsker å generere alle permutasjoner for en sekvens av fire elementer - [1, 2, 3, 4]. Så det vil være 24 permutasjoner. Illustrasjonen nedenfor presenterer de delvise trinnene i algoritmen:

Hver node i treet kan forstås som en tilstand. De røde sifrene over toppen indikerer indeksen for det bearbeidede elementet. De grønne sifrene i nodene illustrerer bytter.

Så vi begynner i staten [1, 2, 3, 4] med en indeks lik null. Vi bytter det første elementet med hvert element - inkludert det første som ikke bytter noe - og går videre til neste tilstand.

Nå er våre ønskede permutasjoner plassert i den siste kolonnen til høyre.

2.2. Java-implementering

Algoritmen skrevet i Java er kort:

private statiske ugyldige permutasjonerIntern (Listesekvens, List resultater, int-indeks) {if (index == sequence.size () - 1) {permutations.add (new ArrayList (sequence)); } for (int i = indeks; i <sekvens.størrelse (); i ++) {bytte (sekvens, i, indeks); permutasjonerIntern (sekvens, permutasjoner, indeks + 1); bytte (sekvens, i, indeks); }}

Vår funksjon tar tre parametere: den nåværende behandlede sekvensen, resultater (permutasjoner) og indeksen til elementet som behandles for øyeblikket.

Det første du må gjøre er å sjekke om vi har nådd det siste elementet. I så fall legger vi til sekvensen i resultatlisten.

Så, i for-loop, utfører vi et bytte, gjør et rekursivt anrop til metoden, og bytter deretter elementet tilbake.

Den siste delen er et lite prestasjonstriks - vi kan operere på det samme sekvens motsette deg hele tiden uten å måtte opprette en ny sekvens for hver rekursive samtale.

Det kan også være lurt å skjule den første rekursive samtalen under en fasademetode:

offentlig statisk liste genererePermutasjoner (Listesekvens) {List permutasjoner = ny ArrayList (); permutasjonerIntern (sekvens, permutasjoner, 0); retur permutasjoner; } 

Husk at algoritmen som vises vil bare fungere for sekvenser av unike elementer! Å bruke samme algoritme for sekvenser med tilbakevendende elementer vil gi oss repetisjoner.

3. Generere Powerset til et sett

Et annet populært problem er å generere et sett med krefter. La oss starte med definisjonen:

styresett (eller maktsett) av settet S er settet med alle delmengder av S inkludert det tomme settet og S seg selv

Så for eksempel gitt et sett [a, b, c]inneholder kretsettet åtte delmengder:

[] [a] [b] [c] [a, b] [a, c] [b, c] [a, b, c]

Vi vet fra matematikk at for et sett som inneholder n elementer, kraftpakken skal inneholde 2 ^ n delmengder. Dette tallet vokser også raskt, men ikke så raskt som faktor.

3.1. Algoritme

Denne gangen vil vi også tenke rekursivt. Nå vil vår tilstand bestå av to ting: indeksen til elementet som for tiden behandles i et sett og en akkumulator.

Vi må ta en avgjørelse med to valg i hver tilstand: om vi skal plassere det nåværende elementet i akkumulatoren eller ikke. Når indeksen vår når slutten av settet, har vi en mulig delmengde. På en slik måte kan vi generere alle mulige delmengder.

3.2. Java-implementering

Algoritmen vår skrevet i Java er ganske lesbar:

private static void powersetInternal (Listesett, Liste powerset, List accumulator, int index) {if (index == set.size ()) {results.add (new ArrayList (accumulator)); } annet {accumulator.add (set.get (index)); powerSetInternal (sett, styresett, akkumulator, indeks + 1); accumulator.remove (accumulator.size () - 1); powerSetInternal (sett, kraftsett, akkumulator, indeks + 1); }}

Vår funksjon tar fire parametere: et sett som vi vil generere delmengder for, den resulterende kraftmengden, akkumulatoren og indeksen til det nå behandlede elementet.

For enkelhets skyld, vi holder settene våre i lister. Vi vil ha rask tilgang til elementer spesifisert av indeks, som vi kan oppnå det med Liste, men ikke med Sett.

I tillegg er et enkelt element representert med en enkelt bokstav (Karakter klasse i Java).

Først sjekker vi om indeksen overstiger den innstilte størrelsen. Hvis det gjør det, setter vi akkumulatoren i resultatsettet, ellers:

  • legg det aktuelle elementet i akkumulatoren
  • ring et rekursivt anrop med inkrementert indeks og utvidet akkumulator
  • fjern det siste elementet fra akkumulatoren, som vi la til tidligere
  • ring en gang til med uendret akkumulator og inkrementert indeks

Igjen skjuler vi implementeringen med en fasademetode:

offentlig statisk liste createPowerset (Listesekvens) {List powerset = ny ArrayList (); powerSetInternal (sekvens, powerset, ny ArrayList (), 0); returmakt; }

4. Generere kombinasjoner

Nå er det på tide å takle kombinasjoner. Vi definerer det som følger:

k-kombinasjon av et sett S er en delmengde av k distinkte elementer fra S, der en ordre på ting ikke betyr noe

Antall k-kombinasjoner er beskrevet av binomialkoeffisienten:

Så for eksempel for settet [a, b, c] vi har tre 2-kombinasjoner:

[a, b] [a, c] [b, c]

Kombinasjoner har mange kombinasjonsbruk og forklaringer. La oss si et eksempel, vi har en fotballiga som består av 16 lag. Hvor mange forskjellige kamper kan vi se?

Svaret er , som evalueres til 120.

4.1. Algoritme

Konseptuelt vil vi gjøre noe som ligner på den forrige algoritmen for powersets. Vi har en rekursiv funksjon, med tilstand som består av indeksen til det for tiden behandlede elementet og en akkumulator.

Igjen har vi den samme avgjørelsen for hver stat: Legger vi til elementet i akkumulatoren?Denne gangen har vi imidlertid en ekstra begrensning - akkumulatoren vår kan ikke ha mer enn k elementer.

Det er verdt å merke seg at den binomiale koeffisienten ikke nødvendigvis trenger å være et stort antall. For eksempel:

er lik 4,950, mens

har 30 sifre!

4.2. Java-implementering

For enkelhets skyld antar vi at elementene i vårt sett er heltall.

La oss ta en titt på Java-implementeringen av algoritmen:

private statiske ugyldige kombinasjoner Internt (List inputSet, int k, List results, ArrayList accumulator, int index) {int needToAccumulate = k - accumulator.size (); int canAcculumate = inputSet.size () - indeks; hvis (accumulator.size () == k) {results.add (ny ArrayList (akkumulator)); } annet hvis (needToAccumulate <= canAcculumate) {kombinasjonerIntern (inputSet, k, resultater, akkumulator, indeks + 1); accumulator.add (inputSet.get (indeks)); kombinasjonerIntern (inputSet, k, resultater, akkumulator, indeks + 1); accumulator.remove (accumulator.size () - 1); }}

Denne gangen har funksjonen vår fem parametere: et inngangssett, k parameter, en resultatliste, en akkumulator og indeksen til det for tiden behandlede elementet.

Vi starter med å definere hjelpervariabler:

  • needToAccumulate - indikerer hvor mange flere elementer vi trenger å legge til i akkumulatoren vår for å få en riktig kombinasjon
  • kanAkkumulere - indikerer hvor mange flere elementer vi kan legge til i akkumulatoren vår

Nå sjekker vi om akkumulatorstørrelsen vår er lik k. I så fall kan vi sette den kopierte matrisen i resultatlisten.

I et annet tilfelle, hvis vi fremdeles har nok elementer i den gjenværende delen av settet, foretar vi to separate rekursive samtaler: med og uten at det nå behandlede elementet blir satt i akkumulatoren. Denne delen er analog med hvordan vi genererte powerset tidligere.

Selvfølgelig kunne denne metoden blitt skrevet for å fungere litt raskere. For eksempel kan vi erklære needToAccumulate og kanAkkumulere variabler senere. Vi er imidlertid fokusert på lesbarhet.

Igjen skjuler en fasademetode implementeringen:

offentlig statisk liste kombinasjoner (List inputSet, int k) {List resultater = ny ArrayList (); combinedInternal (inputSet, k, results, new ArrayList (), 0); returnere resultater; }

5. Sammendrag

I denne artikkelen har vi diskutert forskjellige kombinatoriske problemer. I tillegg har vi vist enkle algoritmer for å løse dem med implementeringer i Java. I noen tilfeller kan disse algoritmene hjelpe til med uvanlige testbehov.

Som vanlig er den komplette kildekoden, med tester, tilgjengelig på GitHub.