streamalism.org

1. Pregled

U ovom uputstvu naučit ćemo kako riješiti nekoliko uobičajenih kombinatornih problema. Najvjerojatnije nisu vrlo korisni u svakodnevnom poslu; međutim, oni su zanimljivi iz algoritamske perspektive. Možda će nam biti korisni za potrebe testiranja.

Imajte na umu da postoji mnogo različitih pristupa rješavanju ovih problema. Pokušali smo učiniti predstavljena rješenja jednostavnima za dohvat.

2. Generiranje permutacija

Prvo, krenimo s permutacijama. Permutacija je čin preslagivanja niza na takav način da ima drugačiji redoslijed.

Kao što znamo iz matematike, za slijed od n elementi, postoje n! različite permutacije. n! je poznata kao faktorska operacija:

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

Tako, na primjer, za slijed [1, 2, 3] postoji šest permutacija:

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

Factorial raste vrlo brzo - za niz od 10 elemenata imamo 3.628.800 različitih permutacija! U ovom slučaju, govorimo o permuting sekvencama, gdje je svaki pojedini element različit.

2.1. Algoritam

Dobra je ideja razmišljati o generiranju permutacija na rekurzivan način. Uvedimo ideju države. Sastojat će se od dvije stvari: trenutne permutacije i indeksa trenutno obrađenog elementa.

Jedini posao koji treba obaviti u takvom stanju je zamijeniti element sa svakim preostalim i izvršiti prijelaz u stanje s modificiranim redoslijedom i indeksom povećanim za jedan.

Ilustrirajmo na primjeru.

Želimo generirati sve permutacije za niz od četiri elementa - [1, 2, 3, 4]. Dakle, bit će 24 permutacije. Ilustracija u nastavku prikazuje djelomične korake algoritma:

Svaki čvor stabla može se shvatiti kao stanje. Crvene znamenke na vrhu označavaju indeks trenutno obrađenog elementa. Zelene znamenke u čvorovima prikazuju zamjene.

Dakle, počinjemo u državi [1, 2, 3, 4] s indeksom jednakim nuli. Zamijenimo prvi element sa svakim elementom - uključujući i prvi, koji ništa ne mijenja - i prelazimo u sljedeće stanje.

Sada su naše željene permutacije smještene u posljednjem stupcu s desne strane.

2.2. Implementacija Jave

Algoritam napisan na Javi kratak je:

privatne statičke praznine permutacijeInternal (Slijed popisa, Popis rezultati, int indeks) {if (index == sequence.size () - 1) {permutacije.add (novi ArrayList (niz)); } for (int i = index; i <sequence.size (); i ++) {swap (slijed, i, indeks); permutacijeInterna (slijed, permutacije, indeks + 1); zamjena (slijed, i, indeks); }}

Naša funkcija uzima tri parametra: trenutno obrađeni slijed, rezultate (permutacije) i indeks elementa koji se trenutno obrađuje.

Prvo što treba učiniti je provjeriti jesmo li stigli do posljednjeg elementa. Ako je tako, dodamo slijed na popis rezultata.

Zatim, u for-loop, izvodimo zamjenu, vršimo rekurzivni poziv metode i zatim zamjenjujemo element natrag.

Posljednji dio je mali trik u izvedbi - možemo operirati isti slijed objekt cijelo vrijeme bez potrebe za stvaranjem nove sekvence za svaki rekurzivni poziv.

Također bi mogla biti dobra ideja sakriti prvi rekurzivni poziv fasadnom metodom:

javni statični Popis generiraj Permutacije (slijed popisa) {Popis permutacije = novi ArrayList (); permutacijeInterna (slijed, permutacije, 0); povratne permutacije; } 

Imajte na umu da će prikazani algoritam raditi samo za sekvence jedinstvenih elemenata! Primjena istog algoritma za sekvence s ponavljajućim elementima dat će nam ponavljanja.

3. Generiranje Powerseta skupa

Još jedan popularan problem je generiranje power set-a. Počnimo s definicijom:

powerset (ili set napajanja) skupa S je skup svih podskupova S uključujući prazan skup i S sebe

Tako, na primjer, s obzirom na skup [a, b, c], powerset sadrži osam podskupina:

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

Iz matematike znamo da za skup koji sadrži n elementi, powerset treba sadržavati 2 ^ n podskupovi. Ovaj broj također brzo raste, ali ne tako brzo kao faktorijel.

3.1. Algoritam

Ovaj put ćemo razmišljati i rekurzivno. Sada će se naše stanje sastojati od dvije stvari: indeksa elementa koji se trenutno obrađuje u skupu i akumulatora.

Moramo donijeti odluku s dva izbora u svakom stanju: hoćemo li staviti trenutni element u akumulator ili ne. Kad naš indeks dosegne kraj skupa, imamo jedan mogući podskup. Na takav način možemo generirati sve moguće podskupine.

3.2. Implementacija Jave

Naš algoritam napisan na Javi prilično je čitljiv:

private static void powersetInternal (Popis postavljen, Popis powerset, akumulator popisa, int indeks) {if (index == set.size ()) {results.add (novi ArrayList (akumulator)); } else {akumulator.add (set.get (indeks)); powerSetInternal (set, powerset, akumulator, indeks + 1); akumulator.remove (akumulator.veličina () - 1); powerSetInternal (set, powerset, akumulator, indeks + 1); }}

Naša funkcija uzima četiri parametra: skup za koji želimo generirati podskupine, rezultirajući skup napajanja, akumulator i indeks trenutno obrađenog elementa.

Za jednostavnost, držimo svoje skupove na popisima. Želimo imati brz pristup elementima navedenim indeksom, kojim to možemo postići Popis, ali ne sa Postavi.

Uz to, jedan je element predstavljen jednim slovom (Lik razred na Javi).

Prvo provjeravamo prelazi li indeks postavljenu veličinu. Ako se dogodi, akumulator stavljamo u skup rezultata, u suprotnom:

• stavite trenutno razmatrani element u akumulator
• uputiti rekurzivni poziv s povećanim indeksom i proširenim akumulatorom
• uklonite posljednji element iz akumulatora, koji smo prethodno dodali
• ponovno uputite poziv s nepromijenjenim akumulatorom i uvećanim indeksom

Opet, skrivamo implementaciju fasadnom metodom:

javni statični popis generirajPowerset (Slijed popisa) {Popis powerset = novi ArrayList (); powerSetInternal (slijed, powerset, novi ArrayList (), 0); povrat snage; }

4. Stvaranje kombinacija

Sada je vrijeme za rješavanje kombinacija. Definiramo ga na sljedeći način:

k-kombinacija skupa S je podskup od k različiti elementi od S, gdje redoslijed predmeta nije važan

Broj k-kombinacija je opisana binomnim koeficijentom:

Tako, na primjer, za set [a, b, c] imamo troje 2-kombinacije:

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

Kombinacije imaju mnogo kombinacijskih navika i objašnjenja. Kao primjer, recimo da imamo nogometnu ligu koja se sastoji od 16 momčadi. Koliko različitih utakmica možemo vidjeti?

Odgovor je , što procjenjuje na 120.

4.1. Algoritam

Konceptualno ćemo napraviti nešto slično prethodnom algoritmu za powersetove. Imat ćemo rekurzivnu funkciju, sa stanjem koje se sastoji od indeksa trenutno obrađenog elementa i akumulatora.

Opet, imamo istu odluku za svako stanje: Dodamo li element akumulatoru?Međutim, ovaj put imamo dodatno ograničenje - naš akumulator ne može imati više od k elementi.

Vrijedno je primijetiti da binomni koeficijent ne mora nužno biti ogroman broj. Na primjer:

jednak je 4.950, dok

ima 30 znamenki!

4.2. Implementacija Jave

Radi jednostavnosti pretpostavljamo da su elementi u našem skupu cjelobrojni.

Pogledajmo implementaciju Java algoritma:

privatne statičke kombinacije prazninaInternal (Lista ulaznih podataka, int k, Lista rezultati, ArrayList akumulator, int indeks) {int needToAccumulate = k - accumulator.size (); int canAcculumate = inputSet.size () - indeks; if (accumulator.size () == k) {results.add (novi ArrayList (akumulator)); } else if (needToAccumulate <= canAcculumate) {kombinacijeInternal (inputSet, k, rezultati, akumulator, indeks + 1); akumulator.add (inputSet.get (indeks)); kombinacijeInternal (inputSet, k, rezultati, akumulator, indeks + 1); akumulator.remove (akumulator.veličina () - 1); }}

Ovaj put, naša funkcija ima pet parametara: ulazni skup, k parametar, popis rezultata, akumulator i indeks trenutno obrađenog elementa.

Počinjemo s definiranjem pomoćnih varijabli:

• needToAccumulate - označava koliko još elemenata trebamo dodati u naš akumulator da bismo dobili odgovarajuću kombinaciju
• canAcculumate - označava koliko još elemenata možemo dodati u naš akumulator

Sada provjeravamo je li naša veličina akumulatora jednaka k. Ako je tako, tada možemo kopirani niz staviti na popis rezultata.

U drugom slučaju, ako još imamo dovoljno elemenata u preostalom dijelu skupa, izvršit ćemo dva odvojena rekurzivna poziva: sa i bez trenutno obrađenog elementa koji se stavlja u akumulator. Ovaj je dio analogan onome kako smo ranije generirali powerset.

Naravno, za ovu je metodu moglo biti napisano da djeluje malo brže. Na primjer, mogli bismo se izjasniti needToAccumulate i canAcculumate varijable kasnije. Međutim, usredotočeni smo na čitljivost.

Opet, metoda fasade skriva implementaciju:

javni statični popis kombinacije (List inputSet, int k) {Popis rezultati = novi ArrayList (); kombinacijeInternal (inputSet, k, rezultati, novi ArrayList (), 0); vratiti rezultate; }

5. Sažetak

U ovom smo članku razgovarali o različitim kombinacijskim problemima. Pored toga, prikazali smo jednostavne algoritme za njihovo rješavanje implementacijama u Javi. U nekim slučajevima ti algoritmi mogu pomoći u neuobičajenim potrebama testiranja.

Kao i obično, cjeloviti izvorni kod s testovima dostupan je na GitHubu.