streamalism.org

1. Áttekintés

Ebben az oktatóanyagban megtudhatjuk, hogyan lehet megoldani néhány gyakori kombinatorikus problémát. Nagy valószínűséggel nem mindennapi munkában hasznosak; algoritmikus szempontból azonban érdekesek. Hasznosnak találhatjuk őket tesztelési célokra.

Ne feledje, hogy sokféle megközelítés létezik e problémák megoldására. Igyekeztünk a bemutatott megoldásokat könnyen megfoghatóvá tenni.

2. Permutációk generálása

Először kezdjük a permutációkkal. A permutáció egy szekvencia átrendezésének olyan művelete, amely más sorrendű.

Mint a matematikából tudjuk, sorozatához n elemek vannak n! különböző permutációk. n! tényező műveletként ismert:

n! = 1 * 2 *… * n

Tehát például egy sorrendhez [1, 2, 3] hat permutáció létezik:

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

A Factorial nagyon gyorsan növekszik - 10 elemből álló sorozat esetén 3 628 800 különböző permutációnk van! Ebben az esetben, permutáló szekvenciákról beszélünk, ahol minden egyes elem más és más.

2.1. Algoritmus

Célszerű elgondolkodni a permutációk rekurzív módon történő előállításán. Mutassuk be az állam gondolatát. Két dologból áll: az aktuális permutációból és az éppen feldolgozott elem indexéből.

Az egyetlen munka, amelyet ilyen állapotban kell elvégezni, az elem cseréje minden megmaradóval, és egy átmenet végrehajtása a módosított szekvenciával és az eggyel megnövelt indexszel.

Szemléltessünk egy példával.

Az összes permutációt négy elemből álló sorozatra szeretnénk generálni - [1, 2, 3, 4]. Tehát 24 permutáció lesz. Az alábbi ábra az algoritmus részleges lépéseit mutatja be:

A fa minden csomópontja állapotként értelmezhető. A tetején lévő piros számjegyek jelzik az éppen feldolgozott elem indexét. A csomópontok zöld számjegyei a csereügyleteket szemléltetik.

Tehát az államban kezdjük [1, 2, 3, 4] nullával egyenlő indexszel. Minden elemgel felcseréljük az első elemet - beleértve az elsőt is, amely semmit sem cserél - és továbblépünk a következő állapotba.

Most a kívánt permutációink a jobb oldali utolsó oszlopban találhatók.

2.2. Java implementáció

A Java-ban írt algoritmus rövid:

belső statikus void permutációk: Belső (Lista sorrend, Lista eredmények, int index) {if (index == szekvencia.méret () - 1) {permutációk.add (új ArrayList (szekvencia)); } for (int i = index; i <szekvencia.méret (); i ++) {csere (szekvencia, i, index); permutationsInternal (szekvencia, permutációk, index + 1); csere (szekvencia, i, index); }}

Funkciónknak három paramétere van: az éppen feldolgozott sorrend, az eredmények (permutációk) és a jelenleg feldolgozott elem indexe.

Az első dolog, hogy ellenőrizze, hogy elértük-e az utolsó elemet. Ha igen, akkor hozzáadjuk a sorrendet az eredménylistához.

Ezután a for-ciklusban cserét hajtunk végre, rekurzív hívást hajtunk végre a metódusra, majd visszacseréljük az elemet.

Az utolsó rész egy kis teljesítménytrükk - ugyanezt működtethetjük sorrend objektumot állandóan anélkül, hogy minden rekurzív híváshoz új sorrendet kellene létrehozni.

Jó ötlet lehet az első rekurzív hívást elrejteni egy homlokzati módszer alatt:

nyilvános statikus lista generatorPermutations (Lista szekvencia) {Lista permutációk = new ArrayList (); permutationsInternal (szekvencia, permutációk, 0); visszatérő permutációk; } 

Ne feledje, hogy a bemutatott algoritmus csak egyedi elemek sorozatainál fog működni! Ha ugyanazt az algoritmust alkalmazzuk ismétlődő elemekkel rendelkező szekvenciákra, ismétléseket kapunk.

3. Egy készlet energiaellátásának létrehozása

Egy másik népszerű probléma a halmaz teljesítményének generálása. Kezdjük a definícióval:

a készlet poweret (vagy power készletet) S az összes részhalmaza S beleértve az üres készletet és S maga

Tehát például adott egy halmaz [a, b, c], a PowerSet nyolc részhalmazot tartalmaz:

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

Matematikából tudjuk, hogy egy olyan készlet esetén n elemek, a poweret-nek tartalmaznia kell 2 ^ n részhalmazok. Ez a szám is gyorsan növekszik, azonban nem olyan gyorsan, mint a faktoriális.

3.1. Algoritmus

Ezúttal rekurzív módon is gondolkodunk. Az állapotunk most két dologból áll: a halmazban jelenleg feldolgozott elem indexéből és egy akkumulátorból.

Minden államban két választással kell döntenünk: az aktuális elemet az akkumulátorba helyezzük-e vagy sem. Amikor indexünk eléri a halmaz végét, van egy lehetséges részhalmazunk. Ily módon minden lehetséges részhalmazt előállíthatunk.

3.2. Java implementáció

Java-ban írt algoritmusunk elég jól olvasható:

privát statikus void powersetInternal (Lista készlet, Lista PowerSet, List akkumulátor, int index) {if (index == set.size ()) {results.add (új ArrayList (akkumulátor)); } else {accumulator.add (set.get (index)); powerSetInternal (készlet, poweret, akkumulátor, index + 1); accumulator.remove (accumulator.size () - 1); powerSetInternal (készlet, poweret, akkumulátor, index + 1); }}

Funkciónknak négy paramétere van: egy halmaz, amelyhez részhalmazokat akarunk létrehozni, az így létrejövő teljesítménykészlet, az akkumulátor és az éppen feldolgozott elem indexe.

Az egyszerűség kedvéért, halmazainkat listákban tartjuk. Gyors hozzáférést szeretnénk elérni az index által meghatározott elemekhez, amellyel elérhetjük Lista, de nem Készlet.

Ezenkívül egyetlen elemet egyetlen betű (karakter osztály Java-ban).

Először ellenőrizzük, hogy az index meghaladja-e a beállított méretet. Ha ez megtörténik, akkor az akkumulátort az eredményhalmazba helyezzük, különben:

• tegye a jelenleg figyelembe vett elemet az akkumulátorba
• indítson rekurzív hívást növelt indexű és kiterjesztett akkumulátorral
• távolítsa el az akkumulátor utolsó elemét, amelyet korábban hozzáadtunk
• hívjon újra változatlan akkumulátorral és növelt indexszel

Ismét elrejtjük a megvalósítást homlokzati módszerrel:

nyilvános statikus lista generatorPowerset (Lista szekvencia) {Lista poweret = új ArrayList (); powerSetInternal (szekvencia, poweret, új ArrayList (), 0); visszatérő áramkör; }

4. Kombinációk generálása

Itt az ideje kezelni a kombinációkat. A következőképpen definiáljuk:

k-halmaz kombinációja S a k különböző elemek S, ahol a cikkek sorrendje nem számít

Száma k- a kombinációkat a binomiális együttható írja le:

Tehát például a készlethez [a, b, c] nekünk három van 2kombinációk:

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

A kombinációknak sok kombinatorikus felhasználása és magyarázata van. Tegyük fel például, hogy van egy 16 csapatból álló labdarúgó bajnokság. Hány különböző mérkőzést láthatunk?

A válasz , amelynek értéke 120.

4.1. Algoritmus

Fogalmilag valami hasonlót fogunk tenni az előző algoritmushoz a PowerSet-ekhez. Rekurzív függvényünk lesz, amelynek állapota az éppen feldolgozott elem indexéből és egy akkumulátorból áll.

Ismét ugyanazt a döntést kaptuk minden állapotra vonatkozóan: Hozzáadjuk az elemet az akkumulátorhoz?Ezúttal azonban van egy további korlátozásunk - akkumulátorunk nem lehet több, mint k elemek.

Érdemes észrevenni, hogy a binomiális együtthatónak nem feltétlenül kell hatalmas számnak lennie. Például:

egyenlő 4950-vel, míg

30 számjegyből áll!

4.2. Java implementáció

Az egyszerűség kedvéért feltételezzük, hogy a halmazunk elemei egész számok.

Vessünk egy pillantást az algoritmus Java implementációjára:

statikus void kombinációk belső (List inputSet, int k, List eredmények, ArrayList akkumulátor, int index) {int needToAccumulate = k - accumulator.size (); int canAcculumate = inputSet.size () - index; if (accumulator.size () == k) {results.add (new ArrayList (akkumulátor)); } else if (needToAccumulate <= canAcculumate) {kombinációkInternal (inputSet, k, eredmények, akkumulátor, index + 1); accumulator.add (inputSet.get (index)); kombinációkBelső (inputSet, k, eredmények, akkumulátor, index + 1); accumulator.remove (accumulator.size () - 1); }}

Ezúttal a funkciónknak öt paramétere van: egy bemeneti készlet, k paraméter, eredménylista, akkumulátor és az éppen feldolgozott elem indexe.

A segítő változók meghatározásával kezdjük:

• needToAccumulate - jelzi, hogy hány elemet kell még hozzáadni az akkumulátorunkhoz, hogy megfelelő kombinációt kapjunk
• canAcculumate - jelzi, hogy hány elemet tudunk még hozzáadni az akkumulátorunkhoz

Most ellenőrizzük, hogy az akkumulátorunk mérete megegyezik-e k. Ha igen, akkor felvehetjük a másolt tömböt az eredménylistába.

Egy másik esetben ha a készlet fennmaradó részében még mindig van elegendő elemünk, két külön rekurzív hívást indítunk: az éppen feldolgozott elemnek az akkumulátorba történő behelyezésével és anélkül. Ez a rész analóg azzal, ahogyan korábban létrehoztuk a poweret.

Természetesen ezt a módszert meg lehetett volna írni, hogy egy kicsit gyorsabban működjön. Például kijelenthetnénk needToAccumulate és canAcculumate változók később. Azonban az olvashatóságra összpontosítunk.

Ismét egy homlokzati módszer rejti a megvalósítást:

nyilvános statikus lista kombinációk (List inputSet, int k) {Lista eredmények = new ArrayList (); kombinációkInternal (inputSet, k, results, new ArrayList (), 0); visszatérési eredmények; }

5. Összefoglalás

Ebben a cikkben különféle kombinatorikus problémákat vitattunk meg. Emellett bemutattunk egyszerű algoritmusokat, amelyek megoldják őket Java-implementációkkal. Bizonyos esetekben ezek az algoritmusok segíthetnek a szokatlan tesztelési igények kielégítésében.

Szokás szerint a teljes forráskód tesztekkel elérhető a GitHubon.