streamalism.org

1. Uvod

U ovom vodiču, razgovarat ćemo o rješenju problema k-kombinacija u Javi.

Prvo ćemo razgovarati i implementirati rekurzivni i iterativni algoritam za generiranje svih kombinacija zadane veličine. Zatim ćemo pregledati rješenja koristeći uobičajene Java knjižnice.

2. Pregled kombinacija

Jednostavno rečeno, kombinacija je podskup elemenata iz zadanog skupa.

Za razliku od permutacija, redoslijed odabira pojedinih elemenata nije važan. Umjesto toga, samo nas zanima je li određeni element u odabiru.

Na primjer, u kartaškoj igri moramo podijeliti 5 karata iz paketa koji se sastoji od 52 karte. Ne zanima nas redoslijed odabira 5 karata. Nego nas zanima samo koje su karte prisutne u ruci.

Neki problemi zahtijevaju da procijenimo sve moguće kombinacije. Da bismo to učinili, nabrajamo razne kombinacije.

Broj različitih načina za odabir elemenata „r“ iz skupa elemenata „n“ može se matematički izraziti sljedećom formulom:

Stoga broj načina odabira elemenata u najgorem slučaju može eksponencijalno rasti. Stoga za velike populacije možda neće biti moguće nabrojati različite odabire.

U takvim slučajevima možemo nasumično odabrati nekoliko reprezentativnih odabira. Proces se naziva uzorkovanje.

Zatim ćemo pregledati različite algoritme da bismo naveli kombinacije.

3. Rekurzivni algoritmi za generiranje kombinacija

Rekurzivni algoritmi obično rade tako da problem podijele na slične manje probleme. Taj se postupak nastavlja dok ne postignemo završni uvjet, što je ujedno i osnovni slučaj. Tada osnovni slučaj rješavamo izravno.

Razgovarat ćemo o dva načina za podjelu zadatka odabira elemenata iz skupa. Prvi pristup dijeli problem u pogledu elemenata u skupu. Drugi pristup dijeli problem praćenjem samo odabranih elemenata.

3.1. Podjela po elementima u cijelom skupu

Podijelimo zadatak odabira „r ” elementi iz "n ” predmeta pregledavanjem predmeta jedan po jedan. Za svaku stavku u skupu možemo je uključiti u odabir ili isključiti.

Ako uvrstimo prvu stavku, tada moramo odabrati „r – 1″ elementi iz preostalog “n - 1 ″ predmeta. S druge strane, ako odbacimo prvu stavku, tada moramo odabrati “r ” elementi iz preostalog “n - 1 ″ predmeta.

To se matematički može izraziti kao:

Pogledajmo sada rekurzivnu provedbu ovog pristupa:

privatni void pomagač (Popis kombinacija, int podaci [], int početak, int kraj, int indeks) {if (index == data.length) {int [] kombinacija = data.clone (); kombinacije.add (kombinacija); } inače ako (početak <= kraj) {podaci [indeks] = početak; pomagač (kombinacije, podaci, početak + 1, kraj, indeks + 1); pomagač (kombinacije, podaci, početak + 1, kraj, indeks); }}

The pomoćnik metoda upućuje sebi dva rekurzivna poziva. Prvi poziv uključuje trenutni element. Drugi poziv odbacuje trenutni element.

Dalje, napišimo generator kombinacija koristeći ovo pomoćnik metoda:

javni popis generira (int n, int r) {Kombinacije popisa = novi ArrayList (); pomagač (kombinacije, novi int [r], 0, n-1, 0); povratne kombinacije; }

U gornjem kodu, generirati metoda postavlja prvi poziv na pomoćnik metoda i prolazi odgovarajuće parametre.

Dalje, nazovimo ovu metodu za generiranje kombinacija:

Kombinacije popisa = generiraj (N, R); za (kombinacija int []: kombinacije) {System.out.println (Arrays.toString (kombinacija)); } System.out.printf ("generirano% d kombinacija% d stavki iz% d", kombinacije.size (), R, N);

Izvršavanjem programa dobivamo sljedeći izlaz:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] generirao 10 kombinacija 2 predmeta iz 5

Na kraju, napišimo test slučaj:

@Test javna praznina givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount () {SetRecursiveCombinationGenerator generator = novi SetRecursiveCombinationGenerator (); Odabir popisa = generator.generate (N, R); assertEquals (nCr, selection.size ()); }

Lako je primijetiti da je potrebna veličina sloga broj elemenata u skupu. Kada je broj elemenata u skupu velik, recimo, veći od maksimalne dubine sloga poziva, prelit ćemo stek i dobiti ćemo StackOverflowError.

Stoga ovaj pristup ne funkcionira ako je skup ulaza velik.

3.2. Podjela po elementima u kombinaciji

Umjesto praćenja elemenata u ulaznom skupu, zadatak ćemo podijeliti praćenjem stavki u odabiru.

Prvo, poredajmo stavke u ulaznom skupu pomoću indeksa "1" do "n ”. Sada možemo odabrati prvu stavku iz prve “n-r + 1 ″ predmeta.

Pretpostavimo da smo odabrali kth artikal. Zatim moramo odabrati “r - 1 ″ stavke iz preostalog “n - k " stavke indeksirane “k + 1 ″ do "n ”.

Ovaj proces matematički izražavamo kao:

Sljedeći, napišimo rekurzivnu metodu za provedbu ovog pristupa:

privatni void pomagač (Popis kombinacija, int podaci [], int početak, int kraj, int indeks) {if (index == data.length) {int [] kombinacija = data.clone (); kombinacije.add (kombinacija); } else {int max = Math.min (kraj, kraj + 1 - data.length + index); za (int i = start; i <= max; i ++) {podaci [indeks] = i; pomagač (kombinacije, podaci, i + 1, kraj, indeks + 1); }}}

U gornjem kodu, za petlja odabire sljedeću stavku, Zatim, ono naziva pomoćnik () metoda rekurzivno za odabir preostalih predmeta. Zaustavljamo se kad je odabran potreban broj predmeta.

Dalje, upotrijebimo pomoćnik metoda za generiranje odabira:

javni popis generira (int n, int r) {Kombinacije popisa = novi ArrayList (); pomagač (kombinacije, novi int [r], 0, n - 1, 0); povratne kombinacije; }

Na kraju, napišite test:

@Test javna praznina givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount () {SelectionRecursiveCombinationGenerator generator = novi SelectionRecursiveCombinationGenerator (); Odabir popisa = generator.generate (N, R); assertEquals (nCr, selection.size ()); }

Veličina niza poziva koji se koristi ovim pristupom jednaka je broju elemenata u odabiru. Stoga, ovaj pristup može raditi za velike ulaze sve dok je broj elemenata koji će se odabrati manji od maksimalne dubine stoga poziva.

Ako je i broj odabranih elemenata velik, ova metoda neće raditi.

4. Iterativni algoritam

U iterativnom pristupu započinjemo s početnom kombinacijom. Zatim, nastavljamo generirati sljedeću kombinaciju iz trenutne dok ne generiramo sve kombinacije.

Generirajmo kombinacije leksikografskim redoslijedom. Počinjemo s najnižom leksikografskom kombinacijom.

Da bismo dobili sljedeću kombinaciju iz trenutne, pronađemo krajnje pravo mjesto u trenutnoj kombinaciji koje se može povećati. Zatim povećavamo mjesto i generiramo najnižu moguću leksikografsku kombinaciju s desne strane tog mjesta.

Napišimo kod koji slijedi ovaj pristup:

javni popis generira (int n, int r) {Kombinacije popisa = novi ArrayList (); int [] kombinacija = nova int [r]; // inicijalizira se najnižom leksikografskom kombinacijom za (int i = 0; i <r; i ++) {kombinacija [i] = i; } while (kombinacija [r - 1] <n) {kombinacije.add (kombinacija.clone ()); // generiranje sljedeće kombinacije u leksikografskom redoslijedu int t = r - 1; dok (t! = 0 && kombinacija [t] == ​​n - r + t) {t--; } kombinacija [t] ++; za (int i = t + 1; i <r; i ++) {kombinacija [i] = kombinacija [i - 1] + 1; }} kombinacije povratka; }

Dalje, napišimo test slučaj:

@Test javna praznina givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount () {IterativeCombinationGenerator generator = novi IterativeCombinationGenerator (); Odabir popisa = generator.generate (N, R); assertEquals (nCr, selection.size ()); }

Sada ćemo koristiti neke Java knjižnice za rješavanje problema.

5. Java knjižnice koje provode kombinacije

Koliko god je moguće, trebali bismo ponovno upotrijebiti postojeće implementacije knjižnica, umjesto da uvodimo svoje. U ovom ćemo odjeljku istražiti sljedeće Java knjižnice koje implementiraju kombinacije:

• Apache Commons
• Guava
• KombinatorikaLib

5.1. Apache Commons

The KombinatorikaKorisništvo klasa iz Apache Commons nudi mnoge kombinacijske korisne funkcije. Konkretno, kombinacijeIterator metoda vraća iterator koji će generirati kombinacije u leksikografskom redoslijedu.

Prvo, dodajmo ovisnost Mavena commons-math3 projektu:

 org.apache.commons commons-math3 3.6.1 

Sljedeći, iskoristimo kombinacijeIterator metoda za ispis kombinacija:

javna statička praznina generira (int n, int r) {iterator iterator = CombinatoricsUtils.combinationsIterator (n, r); while (iterator.hasNext ()) {final int [] kombinacija = iterator.next (); System.out.println (Arrays.toString (kombinacija)); }}

5.2. Google Guava

The Kompleti klasa iz biblioteke Guava pruža korisne metode za operacije povezane sa skupom. The kombinacije metoda vraća sve podskupove zadane veličine.

Prvo, dodajte projektu ovisnost maven za knjižnicu Guava:

 com.google.guava guava 27.0.1-jre 

Sljedeći, iskoristimo kombinacije metoda za generiranje kombinacija:

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

Ovdje koristimo ImmutableSet.of metoda za stvaranje skupa od zadanih brojeva.

5.3. KombinatorikaLib

CombinatoricsLib je mala i jednostavna Java knjižnica za permutacije, kombinacije, podskupove, cjelobrojne particije i kartezijski proizvod.

Da bismo ga koristili u projektu, dodajmo kombinatorikalib3 Ovisnost o Mavenu:

 com.github.dpaukov kombinatorikalib3 3.3.0 

Sljedeći, iskoristimo knjižnicu za ispis kombinacija:

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

Ovo daje sljedeći izlaz pri izvršenju:

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

Više primjera dostupno je na kombinatorikalib3-primjer.

6. Zaključak

U ovom smo članku implementirali nekoliko algoritama za generiranje kombinacija.

Također smo pregledali nekoliko implementacija knjižnica. Tipično bismo ih koristili umjesto da svoje valjamo.

Kao i obično, puni izvorni kod možete pronaći na GitHubu.