Oversigt over kombinationsproblemer i Java

1. Oversigt

I denne vejledning lærer vi, hvordan man løser et par almindelige kombinatoriske problemer. De er højst sandsynligt ikke særlig nyttige i et dagligt job; de er dog interessante fra det algoritmiske perspektiv. Vi kan finde dem nyttige til testformål.

Husk, at der er mange forskellige tilgange til løsning af disse problemer. Vi har forsøgt at gøre de præsenterede løsninger nemme at forstå.

2. Generering af permutationer

Lad os først starte med permutationer. En permutation er en handling til at omarrangere en sekvens på en sådan måde, at den har en anden rækkefølge.

Som vi ved fra matematik, for en sekvens af n elementer, der er n! forskellige permutationer. n! er kendt som en faktuel operation:

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

Så for eksempel for en sekvens [1, 2, 3] der er seks permutationer:

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

Faktor vokser meget hurtigt - for en sekvens på 10 elementer har vi 3.628.800 forskellige permutationer! I dette tilfælde, vi taler om permuterende sekvenser, hvor hvert enkelt element er forskelligt.

2.1. Algoritme

Det er en god ide at overveje at generere permutationer på en rekursiv måde. Lad os introducere ideen om staten. Det vil bestå af to ting: den aktuelle permutation og indekset for det aktuelt behandlede element.

Det eneste arbejde, der skal udføres i en sådan tilstand, er at bytte elementet med hver resterende og udføre en overgang til en tilstand med den modificerede sekvens og indekset øges med en.

Lad os illustrere med et eksempel.

Vi ønsker at generere alle permutationer for en sekvens af fire elementer - [1, 2, 3, 4]. Så der vil være 24 permutationer. Illustrationen nedenfor viser algoritmens delvise trin:

Hver knude i træet kan forstås som en tilstand. De røde cifre øverst angiver indekset for det aktuelt behandlede element. De grønne cifre i noderne illustrerer swaps.

Så vi starter i staten [1, 2, 3, 4] med et indeks lig med nul. Vi bytter det første element med hvert element - inklusive det første, der intet bytter - og går videre til den næste tilstand.

Nu er vores ønskede permutationer placeret i den sidste kolonne til højre.

2.2. Java-implementering

Algoritmen skrevet i Java er kort:

private statiske ugyldige permutationerIntern (Listesekvens, List resultater, int-indeks) {if (index == sequence.size () - 1) {permutations.add (ny ArrayList (sekvens)); } for (int i = indeks; i <sekvens.størrelse (); i ++) {swap (sekvens, i, indeks); permutationsInternal (sekvens, permutationer, indeks + 1); swap (sekvens, i, indeks); }}

Vores funktion tager tre parametre: den aktuelt behandlede sekvens, resultater (permutationer) og indekset for det element, der aktuelt behandles.

Den første ting at gøre er at kontrollere, om vi har nået det sidste element. I så fald tilføjer vi sekvensen til resultatlisten.

Derefter udfører vi en swap i for-loop, foretager et rekursivt opkald til metoden og bytter derefter elementet tilbage.

Den sidste del er et lille præstationstrick - vi kan operere på det samme sekvens modsætter dig hele tiden uden at skulle oprette en ny sekvens for hvert rekursivt opkald.

Det kan også være en god ide at skjule det første rekursive opkald under en facademetode:

offentlig statisk liste genererePermutationer (Listesekvens) {List permutationer = ny ArrayList (); permutationsInternal (sekvens, permutationer, 0); retur permutationer; } 

Husk, at den viste algoritme kun fungerer for sekvenser af unikke elementer! Anvendelse af den samme algoritme for sekvenser med tilbagevendende elementer giver os gentagelser.

3. Generering af Powerset af et sæt

Et andet populært problem er at generere powersets for et sæt. Lad os starte med definitionen:

poweret (eller power set) for sæt S er sættet med alle delmængder af S inklusive det tomme sæt og S sig selv

Så for eksempel givet et sæt [a, b, c], powersets indeholder otte delmængder:

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

Vi ved fra matematik, at for et sæt, der indeholder n elementer, PowerSet skal indeholde 2 ^ n delmængder. Dette antal vokser også hurtigt, dog ikke så hurtigt som faktorisk.

3.1. Algoritme

Denne gang tænker vi også rekursivt. Nu vil vores tilstand bestå af to ting: indekset for det element, der aktuelt behandles i et sæt og en akkumulator.

Vi er nødt til at træffe en beslutning med to valg i hver stat: om det aktuelle element skal placeres i akkumulatoren eller ej. Når vores indeks når slutningen af ​​sættet, har vi en mulig delmængde. På en sådan måde kan vi generere alle mulige delmængder.

3.2. Java-implementering

Vores algoritme skrevet i Java er ret læsbar:

private static void powersetInternal (List set, List powerset, List akkumulator, int index) {if (index == set.size ()) {results.add (new ArrayList (accumulator)); } andet {accumulator.add (set.get (index)); powerSetInternal (sæt, powerset, akkumulator, indeks + 1); accumulator.remove (accumulator.size () - 1); powerSetInternal (sæt, powerset, akkumulator, indeks + 1); }}

Vores funktion tager fire parametre: et sæt, som vi vil generere delmængder for, det resulterende powerset, akkumulatoren og indekset for det aktuelt behandlede element.

For enkelhedens skyld vi holder vores sæt i lister. Vi vil have hurtig adgang til elementer specificeret af indeks, som vi kan opnå det med Liste, men ikke med Sæt.

Derudover er et enkelt element repræsenteret af et enkelt bogstav (Karakter klasse i Java).

Først kontrollerer vi, om indekset overstiger den indstillede størrelse. Hvis det gør det, sætter vi akkumulatoren i resultatsættet, ellers:

  • sæt det aktuelt betragtede element i akkumulatoren
  • foretage et rekursivt opkald med inkrementeret indeks og udvidet akkumulator
  • fjern det sidste element fra akkumulatoren, som vi tidligere har tilføjet
  • ring et opkald igen med uændret akkumulator og det forøgede indeks

Igen skjuler vi implementeringen med en facademetode:

offentlig statisk liste genererePowerset (Listesekvens) {List powerset = ny ArrayList (); powerSetInternal (sekvens, powerset, ny ArrayList (), 0); returner poweret; }

4. Generering af kombinationer

Nu er det tid til at tackle kombinationer. Vi definerer det som følger:

k-kombination af et sæt S er en delmængde af k forskellige elementer fra S, hvor en ordre på varer ikke betyder noget

Antallet af k-kombinationer er beskrevet med binomialkoefficienten:

Så for eksempel til sættet [a, b, c] vi har tre 2-kombinationer:

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

Kombinationer har mange kombinatoriske anvendelser og forklaringer. Lad os som et eksempel sige, at vi har en fodboldliga, der består af 16 hold. Hvor mange forskellige kampe kan vi se?

Svaret er , som evalueres til 120.

4.1. Algoritme

Konceptuelt vil vi gøre noget, der ligner den tidligere algoritme for powersets. Vi har en rekursiv funktion med tilstand bestående af indekset for det aktuelt behandlede element og en akkumulator.

Igen har vi den samme beslutning for hver stat: Føjer vi elementet til akkumulatoren?Denne gang har vi dog en yderligere begrænsning - vores akkumulator kan ikke have mere end k elementer.

Det er værd at bemærke, at den binomiale koefficient ikke nødvendigvis behøver at være et stort antal. For eksempel:

er lig med 4.950, mens

har 30 cifre!

4.2. Java-implementering

For nemheds skyld antager vi, at elementer i vores sæt er heltal.

Lad os se på Java-implementeringen af ​​algoritmen:

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

Denne gang har vores funktion fem parametre: et indgangssæt, k parameter, en resultatliste, en akkumulator og indekset for det aktuelt behandlede element.

Vi starter med at definere hjælpervariabler:

  • needToAkkumuler - angiver, hvor mange flere elementer vi skal tilføje til vores akkumulator for at få en ordentlig kombination
  • kanAkkumulere - angiver, hvor mange flere elementer vi kan tilføje til vores akkumulator

Nu kontrollerer vi, om vores akkumulatorstørrelse er lig med k. I så fald kan vi placere det kopierede array i resultatlisten.

I et andet tilfælde hvis vi stadig har nok elementer i den resterende del af sættet, foretager vi to separate rekursive opkald: med og uden at det aktuelt behandlede element sættes i akkumulatoren. Denne del er analog med, hvordan vi genererede powerset tidligere.

Selvfølgelig kunne denne metode have været skrevet for at arbejde lidt hurtigere. For eksempel kunne vi erklære needToAkkumuler og kan akkumulere variabler senere. Vi er dog fokuseret på læsbarhed.

Igen skjuler en facademetode implementeringen:

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

5. Resume

I denne artikel har vi diskuteret forskellige kombinatoriske problemer. Derudover har vi vist enkle algoritmer til at løse dem med implementeringer i Java. I nogle tilfælde kan disse algoritmer hjælpe med usædvanlige testbehov.

Som sædvanlig er den komplette kildekode med tests tilgængelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found