streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban megbeszéljük a k-kombinációk problémájának megoldását a Java-ban.

Először a rekurzív és az iteratív algoritmusokat is megvitatjuk és megvalósítjuk az adott méretű összes kombináció előállításához. Ezután áttekintjük a megoldásokat a közös Java könyvtárak használatával.

2. Kombinációk áttekintése

Egyszerűen fogalmazva, a kombináció egy adott halmaz elemeinek részhalmaza.

A permutációkkal ellentétben az egyes elemek kiválasztásának sorrendje nem számít. Ehelyett csak az érdekel, hogy egy adott elem szerepel-e a kiválasztásban.

Például egy kártyajátékban 5 kártyát kell osztanunk az 52 kártyából álló csomagból. Nem érdekel az 5 kártya kiválasztásának sorrendje. Inkább csak az érdekel, hogy melyik kártya van jelen a kézben.

Néhány probléma megköveteli, hogy értékeljük az összes lehetséges kombinációt. Ennek érdekében felsoroljuk a különféle kombinációkat.

Az „n” elemek halmazából az „r” elemek kiválasztásának különféle módjai matematikailag kifejezhetők a következő képlettel:

Ezért az elemek kiválasztásának módjai a legrosszabb esetben exponenciálisan növekedhetnek. Ennélfogva nagy populációk esetében nem biztos, hogy fel lehet sorolni a különböző szelekciókat.

Ilyen esetekben véletlenszerűen választhatunk ki néhány reprezentatív választást. A folyamatot ún mintavétel.

Ezután áttekintjük a különböző algoritmusokat a kombinációk felsorolásához.

3. Rekurzív algoritmusok kombinációk előállításához

A rekurzív algoritmusok általában úgy működnek, hogy egy problémát hasonló kisebb problémákra osztanak fel. Ez a folyamat addig folytatódik, amíg el nem érjük a befejező feltételt, ami szintén alapeset. Ezután közvetlenül megoldjuk az alapesetet.

Két elemet fogunk megvitatni, hogy fel lehessen osztani az elemeket egy készletből. Az első megközelítés a problémát a halmaz elemeire osztja. A második megközelítés csak a kiválasztott elemek követésével osztja meg a problémát.

3.1. Felosztás a teljes készlet elemei szerint

Osszuk meg a „r ” elemekn ” tételeket úgy, hogy egyesével megvizsgálja az elemeket. A készlet minden eleméhez vagy felvehetjük a kiválasztásba, vagy kizárhatjuk.

Ha beletesszük az első tételt, akkor ki kell választanunk az „r – 1″ elemek a fennmaradón - 1 ″ elemeket. Másrészről, ha elvetjük az első tételt, akkor ki kell választanunkr ” elemek a fennmaradón - 1 ″ elemeket.

Ez matematikailag kifejezhető:

Most vizsgáljuk meg ennek a megközelítésnek a rekurzív megvalósítását:

private void helper (Listakombinációk, int adatok [], int kezdet, int vég, int index) {if (index == adat.hossz) {int [] kombináció = adatok.klón (); kombinációk.add (kombináció); } else if (kezdet <= vég) {data [index] = kezdet; segítő (kombinációk, adatok, kezdet + 1, vég, index + 1); segítő (kombinációk, adatok, kezdet + 1, vég, index); }}

A segítő metódus két rekurzív hívást kezdeményez magának. Az első hívás az aktuális elemet tartalmazza. A második hívás elveti az aktuális elemet.

Ezután írjuk meg a kombinációs generátort ezzel segítő módszer:

public List generator (int n, int r) {List kombinációk = new ArrayList (); segítő (kombinációk, új int [r], 0, n-1, 0); visszatérési kombinációk; }

A fenti kódban az generál módszer beállítja az első hívást a segítő módszerrel, és átadja a megfelelő paramétereket.

Ezután hívjuk meg ezt a módszert kombinációk létrehozására:

Listakombinációk = generál (N, R); for (int [] kombináció: kombinációk) {System.out.println (Tömbök.String (kombináció)); } System.out.printf ("% d elem% d kombinációjának generálása% d-ből% d-ből", kombinációk.size (), R, N);

A program futtatásakor a következő kimenetet kapjuk:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] generált 2 kombináció 10 elemet az 5-ből

Végül írjuk meg a tesztesetet:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount () {SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator (); Listaválasztás = generátor.generate (N, R); assertEquals (nCr, selection.size ()); }

Könnyű megfigyelni, hogy a halom szükséges mérete a készletben lévő elemek száma. Ha a halmazban lévő elemek száma nagy, mondjuk nagyobb, mint a hívásverem maximális mélysége, akkor túlcsordítjuk a köteget, és kapunk egy StackOverflowError.

Ezért ez a megközelítés nem működik, ha a bemeneti halmaz nagy.

3.2. Felosztás a kombináció elemei szerint

Ahelyett, hogy nyomon követné a bemeneti halmaz elemeit, felosztjuk a feladatot a kijelölt elemek nyomon követésével.

Először rendeljük meg a bemeneti halmaz elemeit az „1” és „n ”. Most kiválaszthatjuk az első tételt az elsőn-r + 1 " elemeket.

Tegyük fel, hogy a kth tétel. Aztán ki kell választanunkr - 1 " elemek a fennmaradón - k ” indexelt tételekk + 1 " nak nek "n ”.

Ezt a folyamatot matematikailag fejezzük ki:

Következő, írjuk meg a rekurzív módszert ennek a megközelítésnek a megvalósításához:

private void helper (Listakombinációk, int adatok [], int kezdet, int vég, int index) {if (index == adat.hossz) {int [] kombináció = adatok.klón (); kombinációk.add (kombináció); } else {int max = Math.min (vég, vég + 1 - adat.hossz + index); for (int i = start; i <= max; i ++) {adatok [index] = i; segítő (kombinációk, adatok, i + 1, vég, index + 1); }}}

A fenti kódban az mert hurok választja a következő elemet, majd hívja a segítő() módszer rekurzív módon a többi elem kiválasztásához. Megállunk, amikor a szükséges számú elemet kiválasztottuk.

Ezután használjuk a segítő módszer a kiválasztások előállítására:

public List generator (int n, int r) {List kombinációk = new ArrayList (); segítő (kombinációk, új int [r], 0, n - 1, 0); visszatérési kombinációk; }

Végül írjunk egy tesztesetet:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount () {SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator (); Listaválasztás = generátor.generate (N, R); assertEquals (nCr, selection.size ()); }

Az ezzel a megközelítéssel használt hívásverem-méret megegyezik a kijelölt elemek számával. Ebből kifolyólag, ez a megközelítés akkor működik nagy bemeneteknél, ha a kiválasztandó elemek száma kisebb, mint a hívásverem maximális mélysége.

Ha a választandó elemek száma is nagy, akkor ez a módszer nem fog működni.

4. Iteratív algoritmus

Az iteratív megközelítésben egy kezdeti kombinációval indulunk. Azután, addig generáljuk a következő kombinációt az aktuálisból, amíg nem állítjuk elő az összes kombinációt.

Generáljuk a kombinációkat lexikográfiai sorrendben. A legalacsonyabb lexikográfiai kombinációval kezdjük.

Annak érdekében, hogy a következő kombinációt az aktuálisból kapjuk, megtaláljuk az aktuális kombinációban a jobb szélső helyet, amely növelhető. Ezután növeljük a helyet, és a lehető legalacsonyabb lexikográfiai kombinációt generáljuk a helytől jobbra.

Írjuk meg a kódot, amely ezt a megközelítést követi:

public List generator (int n, int r) {List kombinációk = new ArrayList (); int [] kombináció = új int [r]; // inicializálás a legalacsonyabb lexikográfiai kombinációval a (int i = 0; i <r; i ++) {kombinációhoz [i] = i; } while (kombináció [r - 1] <n) {kombinációk.add (kombináció.klón ()); // következő kombináció generálása lexikográfiai sorrendben int t = r - 1; míg (t! = 0 && kombináció [t] == ​​n - r + t) {t--; } kombináció [t] ++; for (int i = t + 1; i <r; i ++) {kombináció [i] = kombináció [i - 1] + 1; }} visszatérési kombinációk; }

Ezután írjuk meg a tesztesetet:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount () {IterativeCombinationGenerator generator = new IterativeCombinationGenerator (); Listaválasztás = generátor.generate (N, R); assertEquals (nCr, selection.size ()); }

Most használjunk néhány Java-könyvtárat a probléma megoldására.

5. Java könyvtárak kombinációk megvalósítása

Amennyire lehetséges, a meglévő könyvtári megvalósításokat újra fel kell használnunk a sajátunk bevezetése helyett. Ebben a szakaszban a következő Java könyvtárakat tárjuk fel, amelyek kombinációkat valósítanak meg:

• Apache Commons
• Gujávafa
• KombinatorikaLib

5.1. Apache Commons

A CombinatoricsUtils Az Apache Commons osztály számos kombinált segédfunkciót kínál. Különösen a kombinációkIterátor A method egy iterátort ad vissza, amely lexikográfiai sorrendben generál kombinációkat.

Először tegyük hozzá a Maven-függőséget commons-math3 a projekthez:

 org.apache.commons commons-math3 3.6.1 

Következő, használjuk a kombinációkIterátor módszer a kombinációk kinyomtatására:

public static void generáló (int n, int r) {Iterator iterator = CombinatoricsUtils.combinationsIterator (n, r); while (iterator.hasNext ()) {final int [] kombináció = iterator.next (); System.out.println (Tömbök.String (kombináció)); }}

5.2. Google Guava

A Készletek osztály a guavai könyvtárból nyújt hasznos módszereket a halmazhoz kapcsolódó műveletekhez. A kombinációk metódus egy adott méretű összes részhalmazot ad vissza.

Először tegyük fel a projektbe a guava könyvtár függőleges függőségét:

 com.google.guava guava 27.0.1-jre 

Következő, használjuk a kombinációk módszer kombinációk előállítására:

Készlet kombinációk = Készletek.com kombinációk (ImmutableSet.of (0, 1, 2, 3, 4, 5), 3);

Itt használjuk a ImmutableSet.of módszer a megadott számokból halmaz létrehozására.

5.3. KombinatorikaLib

A CombinatoricsLib egy kicsi és egyszerű Java könyvtár permutációkhoz, kombinációkhoz, részhalmazokhoz, egész partíciókhoz és derékszögű termékhez.

A projektben való felhasználáshoz adjuk hozzá a combinatoricslib3 Maven-függőség:

 com.github.dpaukov combinatoricslib3 3.3.0 

Következő, használjuk a könyvtárat a kombinációk kinyomtatásához:

Generator.combináció (0, 1, 2, 3, 4, 5) .egyszerű (3) .stream () .forEach (System.out :: println);

Ez a következő kimenetet eredményezi végrehajtáskor:

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

További példák a következő címen érhetők el: combinatoricslib3-példa.

6. Következtetés

Ebben a cikkben néhány algoritmust valósítottunk meg kombinációk előállítására.

Néhány könyvtári megvalósítást is áttekintettünk. Általában ezeket használnánk, ahelyett, hogy a sajátunkat görgetnénk.

Szokás szerint a teljes forráskód megtalálható a GitHubon.