streamalism.org

1. Úvod

V tomto návode prediskutujeme riešenie problému k-kombinácií v Jave.

Najskôr prediskutujeme a implementujeme rekurzívne aj iteračné algoritmy na vygenerovanie všetkých kombinácií danej veľkosti. Potom preskúmame riešenia využívajúce bežné knižnice Java.

2. Prehľad kombinácií

Jednoducho povedané, kombinácia je podmnožinou prvkov z danej množiny.

Na rozdiel od permutácií nezáleží na poradí, v akom vyberáme jednotlivé prvky. Namiesto toho nám záleží iba na tom, či je vo výbere konkrétny prvok.

Napríklad v kartovej hre musíme rozdať 5 kariet z balíka pozostávajúceho z 52 kariet. Nemáme záujem o poradie, v akom bolo vybraných 5 kariet. Skôr nám záleží len na tom, ktoré karty sú v ruke.

Niektoré problémy si vyžadujú vyhodnotenie všetkých možných kombinácií. Aby sme to dosiahli, vymenujeme rôzne kombinácie.

Počet odlišných spôsobov výberu prvkov „r“ z množiny prvkov „n“ možno matematicky vyjadriť pomocou tohto vzorca:

Preto počet spôsobov výberu prvkov môže v najhoršom prípade exponenciálne rásť. Preto pre veľké populácie nemusí byť možné vymenovať rôzne výbery.

V takýchto prípadoch môžeme náhodne zvoliť niekoľko reprezentatívnych výberov. Proces sa nazýva vzorkovanie.

Ďalej preskúmame rôzne algoritmy na zostavenie zoznamu kombinácií.

3. Rekurzívne algoritmy na generovanie kombinácií

Rekurzívne algoritmy zvyčajne fungujú tak, že problém rozdelíte na podobné menšie problémy. Tento proces pokračuje, kým nedosiahneme konečnú podmienku, ktorá je tiež základným prípadom. Potom priamo vyriešime základný prípad.

Budeme diskutovať o dvoch spôsoboch, ako rozdeliť úlohu výberu prvkov zo sady. Prvý prístup rozdeľuje problém z hľadiska prvkov v množine. Druhý prístup rozdeľuje problém sledovaním iba vybraných prvkov.

3.1. Delenie na časti podľa prvkov v celej sade

Rozdelme si úlohu výberu „r ” prvky z „n ” položky kontrolovaním jednotlivých položiek. Pre každú položku v sade ju môžeme zahrnúť do výberu alebo vylúčiť.

Ak zahrnieme prvú položku, potom musíme zvoliť „r – 1″ prvky zo zostávajúcich „n - 1 ″ položky. Na druhej strane, ak zahodíme prvú položku, musíme zvoliť „r ” prvkov zo zostávajúcich „n - 1 ″ položky.

To možno matematicky vyjadriť ako:

Teraz sa pozrime na rekurzívnu implementáciu tohto prístupu:

private void helper (Zoznam kombinácií, int dáta [], int začiatok, int koniec, int index) {if (index == data.length) {int [] combination = data.clone (); kombinácie.pridat (kombinacia); } else if (start <= end) {data [index] = start; pomocník (kombinácie, dáta, začiatok + 1, koniec, index + 1); pomocník (kombinácie, dáta, začiatok + 1, koniec, index); }}

The pomocník metóda robí dve rekurzívne volania sama na seba. Prvé volanie obsahuje aktuálny prvok. Druhé volanie zahodí aktuálny prvok.

Ďalej pomocou tohto napíšeme generátor kombinácie pomocník metóda:

public List generate (int n, int r) {List combination = new ArrayList (); pomocník (kombinácie, nový int [r], 0, n-1, 0); návratové kombinácie; }

Vo vyššie uvedenom kóde je generovať metóda nastaví prvé volanie na pomocník metódou a odovzdá príslušné parametre.

Ďalej nazvime túto metódu na generovanie kombinácií:

Zoznam kombinácií = vygenerovať (N, R); pre (int [] kombinácia: kombinácie) {System.out.println (Arrays.toString (kombinácia)); } System.out.printf ("vygenerované% d kombinácie% d položiek z% d", combination.size (), R, N);

Pri vykonávaní programu dostaneme nasledujúci výstup:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] vygeneroval 10 kombinácií 2 položiek z 5

Nakoniec napíšeme testovací prípad:

@ Test public void givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount () {SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator (); Výber zoznamu = generator.generate (N, R); assertEquals (nCr, selection.size ()); }

Je ľahké zistiť, že požadovanou veľkosťou stohu je počet prvkov v sade. Keď je počet prvkov v množine veľký, povedzme väčší ako maximálna hĺbka zásobníka hovorov, zásobník pretečeme a dostaneme StackOverflowError.

Preto tento prístup nefunguje, ak je vstupná množina veľká.

3.2. Rozdelenie podľa prvkov v kombinácii

Namiesto sledovania prvkov vo vstupnej množine úlohu rozdelíme sledovaním položiek vo výbere.

Najskôr usporiadajme položky vo vstupnej množine pomocou indexov „1“ až „n ”. Teraz môžeme vybrať prvú položku z prvej „n-r + 1 ″ položky.

Predpokladajme, že sme si vybrali kth položka. Potom musíme zvoliť „r - 1 ″ položky zo zostávajúcej “n - k ” položky indexované „k + 1 ″ „n ”.

Tento proces vyjadrujeme matematicky ako:

Ďalšie, napíšeme rekurzívnu metódu na implementáciu tohto prístupu:

private void helper (Zoznam kombinácií, int dáta [], int začiatok, int koniec, int index) {if (index == data.length) {int [] combination = data.clone (); kombinácie.pridat (kombinacia); } else {int max = Math.min (end, end + 1 - data.length + index); for (int i = start; i <= max; i ++) {data [index] = i; pomocník (kombinácie, dáta, i + 1, koniec, index + 1); }}}

Vo vyššie uvedenom kóde je pre slučka vyberie nasledujúcu položku, Potom, volá sa to pomocník () metódou rekurzívne na výber zostávajúcich položiek. Zastavíme sa, keď bude vybratý požadovaný počet položiek.

Ďalej použijeme pomocník metóda generovania výberov:

public List generate (int n, int r) {List combination = new ArrayList (); pomocník (kombinácie, nový int [r], 0, n - 1, 0); návratové kombinácie; }

Na záver napíšeme testovací prípad:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExectedCount () {SelectionRecursiveCombinationGenerator generátor = nový SelectionRecursiveCombinationGenerator (); Výber zoznamu = generator.generate (N, R); assertEquals (nCr, selection.size ()); }

Veľkosť zásobníka volaní použitá týmto prístupom je rovnaká ako počet prvkov vo výbere. Preto tento prístup môže fungovať pre veľké vstupy, pokiaľ je počet prvkov, ktoré sa majú zvoliť, menší ako maximálna hĺbka zásobníka hovorov.

Ak je počet prvkov, ktoré sa majú zvoliť, tiež veľký, táto metóda nebude fungovať.

4. Iteratívny algoritmus

Pri iteračnom prístupe začíname počiatočnou kombináciou. Potom, generujeme nasledujúcu kombináciu z aktuálnej, kým nevygenerujeme všetky kombinácie.

Vygenerujme kombinácie v lexikografickom poradí. Začíname s najnižšou lexikografickou kombináciou.

Ak chcete získať nasledujúcu kombináciu z aktuálnej, nájdeme v aktuálnej kombinácii úplne vpravo umiestnenie, ktoré je možné zvýšiť. Potom prírastok miesta a vygenerovanie najnižšej možnej lexikografickej kombinácie napravo od tohto umiestnenia.

Poďme napísať kód, ktorý sleduje tento prístup:

public List generate (int n, int r) {List combination = new ArrayList (); int [] combination = new int [r]; // inicializácia s najnižšou lexikografickou kombináciou pre (int i = 0; i <r; i ++) {combination [i] = i; } while (combination [r - 1] <n) {combination.add (combination.clone ()); // vygenerovanie ďalšej kombinácie v lexikografickom poradí int t = r - 1; while (t! = 0 && kombinácia [t] == ​​n - r + t) {t--; } kombinácia [t] ++; for (int i = t + 1; i <r; i ++) {combination [i] = combination [i - 1] + 1; }} návratové kombinácie; }

Ďalej napíšeme testovací prípad:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount () {IterativeCombinationGenerator generator = nový IterativeCombinationGenerator (); Výber zoznamu = generator.generate (N, R); assertEquals (nCr, selection.size ()); }

Teraz použijeme na vyriešenie problému niektoré knižnice Java.

5. Knižnice Java implementujúce kombinácie

Pokiaľ je to možné, mali by sme namiesto zavedenia vlastných znovu použiť existujúce implementácie knižnice. V tejto časti preskúmame nasledujúce knižnice Java, ktoré implementujú kombinácie:

• Apache Commons
• Guava
• KombinatorikaLib

5.1. Apache Commons

The CombinatoricsUtils triedy od Apache Commons poskytuje mnoho kombinácií užitočných funkcií. Najmä kombinácieIterátor metóda vráti iterátor, ktorý vygeneruje kombinácie v lexikografickom poradí.

Najskôr pridajme závislosť Maven commons-math3 k projektu:

 org.apache.commons commons-math3 3.6.1 

Ďalšie, poďme použiť kombinácieIterátor spôsob tlače kombinácií:

public static void generate (int n, int r) {Iterator iterator = CombinatoricsUtils.combinationsIterator (n, r); while (iterator.hasNext ()) {final int [] combination = iterator.next (); System.out.println (Arrays.toString (kombinácia)); }}

5.2. Google Guava

The Sady trieda z knižnice Guava poskytuje užitočné metódy pre operácie súvisiace so súpravami. The kombinácie metóda vráti všetky podmnožiny danej veľkosti.

Najprv do projektu pridáme závislosť maven pre knižnicu Guava:

 com.google.guava guava 27.0.1-jre 

Ďalšie, poďme použiť kombinácie metóda na generovanie kombinácií:

Nastaviť kombinácie = Sady.kombinácie (ImmutableSet.of (0, 1, 2, 3, 4, 5), 3);

Tu používame ImmutableSet.of metóda na vytvorenie množiny z daných čísel.

5.3. KombinatorikaLib

CombinatoricsLib je malá a jednoduchá knižnica Java pre permutácie, kombinácie, podmnožiny, celé čísla a karteziánsky produkt.

Aby sme ho mohli použiť v projekte, pridajme kombinatoricslib3 Závislosť Maven:

 com.github.dpaukov combineatoricslib3 3.3.0 

Ďalšie, použijeme knižnicu na tlač kombinácií:

Kombinácia generátora (0, 1, 2, 3, 4, 5). Simple (3) .stream () .forEach (System.out :: println);

Pri spustení sa vytvorí tento výstup:

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

Viac príkladov je k dispozícii na stránke kombinatorikalib3-priklad.

6. Záver

V tomto článku sme implementovali niekoľko algoritmov na generovanie kombinácií.

Skontrolovali sme tiež niekoľko implementácií knižnice. Spravidla by sme ich používali namiesto toho, aby sme si rolovali svoje vlastné.

Celý zdrojový kód nájdete ako obvykle na GitHub.