streamalism.org

1. Prehľad

V tomto tutoriále sa dozvieme, ako vyriešiť niekoľko bežných kombinatorických problémov. S najväčšou pravdepodobnosťou nie sú veľmi užitočné v každodennej práci; sú však zaujímavé z pohľadu algoritmu. Možno nám prídu vhod na účely testovania.

Pamätajte, že na riešenie týchto problémov existuje veľa rôznych prístupov. Snažili sme sa, aby boli prezentované riešenia ľahko uchopiteľné.

2. Generovanie permutácií

Najprv začnime s permutáciami. Permutácia je akt zmeny usporiadania sekvencie takým spôsobom, že má iné poradie.

Ako vieme z matematiky, pre postupnosť n prvky, existujú n! rôzne permutácie. n! je známa ako faktoriálna operácia:

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

Teda napríklad pre postupnosť [1, 2, 3] existuje šesť permutácií:

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

Faktoriál rastie veľmi rýchlo - pre postupnosť 10 prvkov máme 3 628 800 rôznych permutácií! V tomto prípade, hovoríme o permutujúcich sekvenciách, kde každý jeden prvok je iný.

2.1. Algoritmus

Je dobré myslieť na generovanie permutácií rekurzívnym spôsobom. Poďme predstaviť myšlienku štátu. Bude sa skladať z dvoch vecí: aktuálna permutácia a index aktuálne spracovávaného prvku.

Jedinou prácou, ktorá sa dá urobiť v takomto stave, je vymeniť prvok za každý zostávajúci a vykonať prechod do stavu s upravenou sekvenciou a indexom zvýšeným o jednu.

Poďme si to ilustrovať na príklade.

Chceme vygenerovať všetky permutácie pre postupnosť štyroch prvkov - [1, 2, 3, 4]. Bude tu teda 24 permutácií. Nasledujúca ilustrácia predstavuje čiastkové kroky algoritmu:

Každý uzol stromu možno chápať ako stav. Červené číslice v hornej časti označujú index aktuálne spracovaného prvku. Zelené číslice v uzloch znázorňujú výmeny.

Takže začíname v štáte [1, 2, 3, 4] s indexom rovným nule. Prvý prvok zameníme za každý prvok - vrátane prvého, ktorý nezmení nič - a presunieme sa do ďalšieho stavu.

Teraz sú naše požadované permutácie umiestnené v poslednom stĺpci vpravo.

2.2. Implementácia Java

Algoritmus napísaný v jazyku Java je krátky:

private static void permutationsInternal (postupnosť zoznamu, zoznam results, int index) {if (index == sequence.size () - 1) {permutations.add (new ArrayList (sequence)); } for (int i = index; i <sequence.size (); i ++) {swap (sekvencia, i, index); permutácieInterné (postupnosť, permutácie, index + 1); swap (postupnosť, i, index); }}

Naša funkcia má tri parametre: aktuálne spracovanú postupnosť, výsledky (permutácie) a index aktuálne spracovávaného prvku.

Prvá vec, ktorú musíte urobiť, je skontrolovať, či sme dosiahli posledný prvok. Ak je to tak, pridáme postupnosť do zoznamu výsledkov.

Potom v cykle for vykonáme zámenu, urobíme rekurzívne volanie metódy a potom zameníme prvok späť.

Posledná časť je malý výkonnostný trik - môžeme pracovať rovnako postupnosť objekt neustále, bez toho, aby ste museli vytvárať novú postupnosť pre každé rekurzívne volanie.

Môže byť tiež dobrý nápad skryť prvé rekurzívne volanie pod metódou fasády:

verejný statický zoznam generatePermutations (Sekvencia zoznamu) {Zoznam permutácie = nový ArrayList (); permutationsInternal (postupnosť, permutácie, 0); návratové permutácie; } 

Nezabudnite, že zobrazený algoritmus bude fungovať iba pre sekvencie jedinečných prvkov! Aplikácia rovnakého algoritmu na sekvencie s opakujúcimi sa prvkami nám prinesie opakovania.

3. Generovanie množiny Powerset množiny

Ďalším populárnym problémom je generovanie množiny síl. Začnime definíciou:

výkonová sada (alebo výkonová sada) súpravy S je množina všetkých podskupín súboru S vrátane prázdnej súpravy a S sám

Takže napríklad daný súbor [a, b, c], sada síl obsahuje osem podmnožín:

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

Z matematiky vieme, že pre množinu obsahujúcich n prvky, množina síl by mala obsahovať 2 ^ n podmnožiny. Toto číslo tiež rýchlo rastie, avšak nie tak rýchlo ako faktoriál.

3.1. Algoritmus

Tentokrát budeme myslieť aj rekurzívne. Náš stav bude teraz pozostávať z dvoch vecí: index prvku, ktorý sa momentálne spracováva v súbore, a akumulátor.

Musíme sa rozhodnúť s dvoma voľbami v každom štáte: či vložiť alebo vložiť aktuálny prvok do akumulátora. Keď náš index dosiahne koniec množiny, máme jednu možnú podmnožinu. Týmto spôsobom môžeme vygenerovať každú možnú podmnožinu.

3.2. Implementácia Java

Náš algoritmus napísaný v prostredí Java je dobre čitateľný:

private static void powersetInternal (Zoznam nastavený, Zoznam powerset, List akumulátor, int index) {if (index == set.size ()) {results.add (nový ArrayList (akumulátor)); } else {akumulator.add (set.get (index)); powerSetInternal (množina, množina síl, akumulátor, index + 1); akumulátor.odstrániť (akumulátor.veľkosť () - 1); powerSetInternal (množina, množina síl, akumulátor, index + 1); }}

Naša funkcia obsahuje štyri parametre: množinu, pre ktorú chceme generovať podmnožiny, výslednú množinu síl, akumulátor a index aktuálne spracovávaného prvku.

Pre jednoduchosť udržujeme naše sady v zoznamoch. Chceme mať rýchly prístup k prvkom špecifikovaným indexom, ktorými to môžeme dosiahnuť Zoznam, ale nie s Nastaviť.

Jeden prvok je navyše reprezentovaný jedným písmenom (Postava triedy v Jave).

Najskôr skontrolujeme, či index presahuje nastavenú veľkosť. Ak áno, vložíme akumulátor do výsledkovej sady, inak:

• vložte momentálne uvažovaný prvok do akumulátora
• uskutočnite rekurzívne volanie s zvýšeným indexom a rozšíreným akumulátorom
• odstráňte posledný prvok z akumulátora, ktorý sme pridali predtým
• znova zavolajte s nezmeneným akumulátorom a zvýšeným indexom

Opäť skryjeme implementáciu metódou fasády:

verejný statický zoznam generatePowerset (postupnosť zoznamu) {zoznam powerset = new ArrayList (); powerSetInternal (postupnosť, množina síl, nový ArrayList (), 0); návratová súprava; }

4. Generovanie kombinácií

Teraz je čas zaoberať sa kombináciami. Definujeme to takto:

k-kombinácia sady S je podmnožina k odlišné prvky od S, kde nezáleží na poradí položiek

Počet k-kombinácie je opísaný binomickým koeficientom:

Teda napríklad pre súpravu [a, b, c] máme tri 2-kombinácie:

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

Kombinácie majú veľa kombinatorických použití a vysvetlení. Ako príklad povedzme, že máme futbalovú ligu zloženú zo 16 tímov. Koľko rôznych zápasov môžeme vidieť?

Odpoveď je , ktorá sa hodnotí na 120.

4.1. Algoritmus

Koncepčne urobíme niečo podobné ako v predchádzajúcom algoritme pre množiny síl. Budeme mať rekurzívnu funkciu so stavom pozostávajúcim z indexu momentálne spracovaného prvku a akumulátora.

Opäť tu máme rovnaké rozhodnutie pre každý štát: Pridáme prvok do akumulátora?Tentokrát však máme ďalšie obmedzenie - náš akumulátor nemôže mať viac ako k prvkov.

Stojí za zmienku, že binomický koeficient nemusí byť nevyhnutne obrovský. Napríklad:

sa rovná 4 950, zatiaľ čo

má 30 číslic!

4.2. Implementácia Java

Pre jednoduchosť predpokladáme, že prvky v našej množine sú celé čísla.

Pozrime sa na implementáciu algoritmu v jazyku Java:

private static void combinationInternal (List inputSet, int k, List výsledky, akumulátor ArrayList, index int)) {int needToAccumulate = k - akumulátor.size (); int canAcculumate = inputSet.size () - index; if (akumulator.size () == k) {results.add (nový ArrayList (akumulátor)); } else if (needToAccumulate <= canAcculumate) {kombinácieInterné (inputSet, k, výsledky, akumulátor, index + 1); akumulator.add (inputSet.get (index)); kombinácieInterné (inputSet, k, výsledky, akumulátor, index + 1); akumulátor.odstrániť (akumulátor.veľkosť () - 1); }}

Tentokrát má naša funkcia päť parametrov: vstupnú sadu, k parameter, zoznam výsledkov, akumulátor a index aktuálne spracovaného prvku.

Začneme definovaním pomocných premenných:

• needToAccumulate - označuje, koľko ďalších prvkov musíme pridať do nášho akumulátora, aby sme dosiahli správnu kombináciu
• canAcculumate - označuje, koľko ďalších prvkov môžeme do nášho akumulátora pridať

Teraz skontrolujeme, či sa veľkosť nášho akumulátora rovná k. Ak je to tak, potom môžeme skopírované pole vložiť do zoznamu výsledkov.

V inom prípade ak máme v zostávajúcej časti množiny ešte dostatok prvkov, uskutočňujeme dve samostatné rekurzívne volania: s alebo bez vloženia aktuálne spracovaného prvku do akumulátora. Táto časť je analogická s tým, ako sme predtým generovali množinu síl.

Samozrejme, táto metóda mohla byť napísaná tak, aby fungovala o niečo rýchlejšie. Napríklad by sme mohli vyhlásiť needToAccumulate a canAcculumate premenné neskôr. Zameriavame sa však na čitateľnosť.

Implementácia opäť skrýva fasádnu metódu:

verejný statický zoznam kombinácie (Zoznam inputSet, int k) {Zoznam results = new ArrayList (); combinationInternal (inputSet, k, results, new ArrayList (), 0); návratové výsledky; }

5. Zhrnutie

V tomto článku sme diskutovali o rôznych kombinatorických problémoch. Ďalej sme ukázali jednoduché algoritmy na ich riešenie pomocou implementácií v Jave. V niektorých prípadoch môžu tieto algoritmy pomôcť pri neobvyklých testovacích požiadavkách.

Kompletný zdrojový kód s testami je ako obvykle k dispozícii na serveri GitHub.