streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban megvizsgáljuk az adott halmaz teljesítménykészletének létrehozásának folyamatát a Java-ban.

Gyors emlékeztetőként, minden mérethez n, van egy teljesítmény-készlet méret 2n. Megtanuljuk, hogyan lehet ezt különböző technikák segítségével megszerezni.

2. A tápegység meghatározása

Egy adott halmaz hatványkészlete S az összes részhalmaza S, beleértve S maga és az üres készlet.

Például egy adott készlethez:

{"APPLE", "NARANCS", "MANGO"}

a teljesítmény beállítása:

{{}, {"APPLE"}, {"NARANCS"}, {"APPLE", "NARANCS"}, {"MANGO"}, {"APPLE", "MANGO"}, {"NARANCS", "MANGO" }, {"APPLE", "NARANCS", "MANGO"}}

Mivel ez is részhalmaz, a belső részhalmazok sorrendje nem fontos, és tetszőleges sorrendben jelenhetnek meg:

{{}, {"MANGO"}, {"ORANGE"}, {"ORANGE", "MANGO"}, {"APPLE"}, {"APPLE", "MANGO"}, {"APPLE", "ORANGE" }, {"APPLE", "NARANCS", "MANGO"}}

3. Guava könyvtár

A Google Guava könyvtár tartalmaz néhány hasznos információt Készlet segédprogramok, például az áramellátás. Így könnyen felhasználhatjuk az adott halmaz teljesítménykészletének megszerzésére is:

@Test public void givenSet_WhenGuavaLibraryGeneratePowerSet_ThenItContainsAllSubsets () {ImmutableSet set = ImmutableSet.of ("APPLE", "ORANGE", "MANGO"); Készlet powerSet = Beállítja.powerSet (meg); Assertions.assertEquals ((1 << set.size ()), powerSet.size ()); MatcherAssert.assertThat (powerSet, Matchers.containsInAnyOrder (ImmutableSet.of (), ImmutableSet.of ("APPLE"), ImmutableSet.of ("ORANGE"), ImmutableSet.of ("APPLE", "ORANGE"), ImmutableSet.of ("MANGO", ImmutableSet.of ("APPLE", "MANGO"), ImmutableSet.of ("ORANGE", "MANGO"), ImmutableSet.of ("APPLE", "ORANGE", "MANGO")) ; }

Gujávafa powerSet belül működik a Iterátor interfész a következő részhalmaz kérésekor kiszámítja és visszaküldi az alkészletet. Tehát a tér bonyolultsága lecsökken Tovább) ahelyett O (2n).

De hogyan érheti el ezt Guava?

4. Teljesítménykészlet-generációs megközelítés

4.1. Algoritmus

Most tárgyaljuk meg a művelet algoritmusának létrehozásának lehetséges lépéseit.

Egy üres halmaz hatványkészlete {{}} amelyben csak egy üres halmazt tartalmaz, tehát ez a legegyszerűbb esetünk.

Minden szetthez S az üres halmazon kívül először kivonunk egy elemet és megnevezzük - elem. Ezután a halmaz többi elemére részhalmazElement nélkül, rekurzív módon kiszámoljuk a beállított teljesítményt - és valami hasonlónak nevezzük el powerSetSubsetWithementElement nélkül. Ezután hozzáadva a kivont elem minden készletbe powerSetSubsetWithementElement nélkül, kapunk powerSetSubsetWithElement.

Most az áramellátás S az unió a powerSetSubsetWithoutElement és a powerSetSubsetWithElement:

Lássunk egy példát az adott halmaz rekurzív teljesítménykészletének veremére {„ALMA”, „NARANCS”, „MANGO”}.

A kép olvashatóságának javítása érdekében rövid névformákat használunk: P a teljesítmény beállítása funkciót és „A”, „O”, „M” rövid formái „ALMA”, „NARANCS”, és "MANGÓ", illetve:

4.2. Végrehajtás

Tehát először írjuk meg a Java kódot egy elem kibontásához, és kapjuk meg a fennmaradó részhalmazokat:

T elem = set.iterator (). Next (); Set subsetWithoutElement = new HashSet (); mert (T s: set) {if (! s.equals (element)) {subsetWithoutElement.add (s); }}

Ezután meg akarjuk szerezni a PowerSet-et részhalmazElement nélkül:

Készlet powersetSubSetWithoutElement = recursivePowerSet (részhalmazWithoutElement);

Ezután vissza kell adnunk azt a poweret az eredetibe:

Készlet powersetSubSetWithElement = new HashSet (); for (Állítsa be a részhalmazWithoutElement: powerSetSubSetWithoutElement) elemet {Set subsetWithElement = új HashSet (részhalmazWithoutElement); részhalmazWithElement.add (elem); powerSetSubSetWithElement.add (részhalmazWithElement); }

Végül a powerSetSubSetWithoutElement és powerSetSubSetWithElement az adott bemeneti készlet teljesítménykészlete:

Készlet powerSet = új HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement);

Ha összes kódrészletünket összerakjuk, láthatjuk a végtermékünket:

nyilvános készlet recursivePowerSet (Set set) {if (set.isEmpty ()) {Set ret = új HashSet (); ret.add (halmaz); visszatér ret; } T elem = set.iterator (). Következő (); Set subSetWithoutElement = getSubSetWithoutElement (halmaz, elem); Készlet powerSetSubSetWithoutElement = recursivePowerSet (subSetWithoutElement); Készlet powerSetSubSetWithElement = addElementToAll (powerSetSubSetWithoutElement, elem); Készlet powerSet = új HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); visszatérő powerSet; } 

4.3. Megjegyzések az egység tesztjeihez

Most teszteljük. Itt van egy kis kritérium a megerősítéshez:

• Először ellenőrizzük a beállított teljesítmény méretét, és annak lennie kell 2n méretkészlethez n.
• Ezután minden elem csak egyszer jelenik meg egy részhalmazban és 2n-1 különböző részhalmazok.
• Végül minden részhalmaznak egyszer kell megjelennie.

Ha ezek a feltételek teljesültek, biztosak lehetünk abban, hogy a funkciónk működik. Most, amióta használtuk Készlet, már tudjuk, hogy nincs ismétlés. Ebben az esetben csak a beállított teljesítmény méretét és az egyes részek előfordulásainak számát kell ellenőriznünk az alhalmazokban.

Az általunk használt teljesítménykészlet méretének ellenőrzéséhez:

MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ())));

És ellenőrizze az egyes elemek előfordulásának számát:

Térképszámláló = új HashMap (); mert (Set set: powerSet) {for (String name: subset) {int szám = számláló.getOrDefault (név, 0); counter.put (név, szám + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ()));

Végül, ha mindent össze tudunk állítani egy egység tesztben:

@Test public void givenSet_WhenPowerSetIsCalculated_ThenItContainsAllSubsets () {Set set = RandomSetOfStringGenerator.generateRandomSet (); Készlet powerSet = új PowerSet (). recursivePowerSet (set); MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ()))); Térképszámláló = új HashMap (); mert (Set set: powerSet) {for (String name: subset) {int szám = számláló.getOrDefault (név, 0); counter.put (név, szám + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ())); }

5. Optimalizálás

Ebben a szakaszban megpróbáljuk minimalizálni a helyet és csökkenteni a belső műveletek számát a beállított teljesítmény optimális kiszámításához.

5.1. Adatszerkezet

Amint az adott megközelítésben láthatjuk, a rekurzív híváshoz sok kivonásra van szükségünk, amely nagy mennyiségű időt és memóriát emészt fel.

Ehelyett az egyes halmazokat vagy részhalmazokat más elképzelésekhez tudjuk hozzárendelni a műveletek számának csökkentése érdekében.

Először egyre nagyobb számot kell rendelnünk 0-tól kezdve az adott halmaz minden objektumához S ami azt jelenti, hogy rendezett számlistával dolgozunk.

Például az adott halmazra {„ALMA”, „NARANCS”, „MANGO”} kapunk:

„ALMA” -> 0

„NARANCS” ->

„MANGO” -> 2

Tehát innentől kezdve a S, generáljuk őket a [0, 1, 2] rendezett listájához, és annak rendezésével szimulálhatjuk a kivonásokat egy kezdő index alapján.

Például, ha a kezdő index értéke 1, ez azt jelenti, hogy létrehozzuk az [1,2] teljesítménykészletet.

A leképezett azonosító lekéréséhez az objektumból és fordítva a tárolás mindkét oldalát tároljuk. Példánk segítségével mindkettőt tároljuk („MANGO” -> 2) és (2 -> „MANGO”). Mivel a számok leképezése nulláról indult, így a fordított térképhez egy egyszerű tömböt használhatunk az adott objektum lekérésére.

Ennek a funkciónak az egyik lehetséges megvalósítása a következő lenne:

privát térkép térkép = new HashMap (); private list fordított térkép = new ArrayList (); private void initizeMap (Gyűjteménygyűjtemény) {int mapId = 0; for (T c: gyűjtemény) {map.put (c, mapId ++); reverseMap.add (c); }}

Az alcsoportok ábrázolásához két jól ismert ötlet van:

1. Index ábrázolás
2. Bináris ábrázolás

5.2. Index ábrázolás

Az egyes részhalmazokat az értékeinek indexe képviseli. Például az adott halmaz index-leképezése {„ALMA”, „NARANCS”, „MANGO”} lenne:

{{} -> {} [0] -> {"APPLE"} [1] -> {"NARANCS"} [0,1] -> {"APPLE", "NARANCS"} [2] -> {" MANGO "} [0,2] -> {" APPLE "," MANGO "} [1,2] -> {" ORANGE "," MANGO "} [0,1,2] -> {" APPLE "," NARANCS "," MANGO "}}

Tehát az adott leképezéssel lekérhetjük a megfelelő halmazt az indexek egy részhalmazából:

privát készlet unMapIndex (Set halmazok) {Készlet ret = új HashSet (); for (Set s: sets) {HashSet részhalmaz = new HashSet (); for (Egész i: s) {részhalmaz.add (fordítottMap.get (i)); } ret.add (részhalmaz); } return ret; }

5.3. Bináris ábrázolás

Vagy reprezentálhatunk minden részhalmazt binárisan. Ha a tényleges halmaz eleme létezik ebben az alkészletben, akkor annak megfelelő értéke 1; különben az 0.

Gyümölcspéldánkban a hatalom a következő lenne:

{[0,0,0] -> {} [1,0,0] -> {"APPLE"} [0,1,0] -> {"NARANCS"} [1,1,0] -> { "APPLE", "ORANGE"} [0,0,1] -> {"MANGO"} [1,0,1] -> {"APPLE", "MANGO"} [0,1,1] -> { "NARANCS", "MANGO"} [1,1,1] -> {"APPLE", "NARANCS", "MANGO"}}

Tehát az adott leképezéssel lekérhetjük a megfelelő halmazt bináris részhalmazból:

privát készlet unMapBinary (Gyűjtemény halmazok) {Készlet ret = új HashSet (); for (Lista s: halmazok) {HashSet részhalmaz = new HashSet (); for (int i = 0; i <s.size (); i ++) {if (s.get (i)) {részhalmaz.add (reverseMap.get (i)); }} ret.add (részhalmaz); } return ret; }

5.4. Rekurzív algoritmus megvalósítása

Ebben a lépésben megpróbáljuk megvalósítani az előző kódot mindkét adatstruktúra segítségével.

Mielőtt meghívnánk ezen funkciók egyikét, meg kell hívnunk a initizeMap módszer a rendezett lista megszerzéséhez. Az adatszerkezetünk létrehozása után meg kell hívnunk a megfelelőt unMap függvény a tényleges objektumok lekéréséhez:

nyilvános készlet recursivePowerSetIndexRepresentation (Gyűjteménykészlet) {initizeMap (készlet); Készlet powerSetIndices = recursivePowerSetIndexRepresentation (0, set.size ()); return unMapIndex (powerSetIndices); }

Tehát próbáljuk ki magunkat az index ábrázolásban:

privát készlet recursivePowerSetIndexRepresentation (int idx, int n) {if (idx == n) {Beállítás üres = új HashSet (); empty.add (új HashSet ()); üresen térjen vissza; } Beállítás powerSetSubset = recursivePowerSetIndexRepresentation (idx + 1, n); Készlet powerSet = új HashSet (powerSetSubset); for (Set s: powerSetSubset) {HashSet subSetIdxInclusive = új HashSet (ek); subSetIdxInclusive.add (idx); powerSet.add (subSetIdxInclusive); } return powerSet; }

Most nézzük meg a bináris megközelítést:

privát készlet recursivePowerSetBinaryRepresentation (int idx, int n) {if (idx == n) {Beállítás powerSetOfEmptySet = új HashSet (); powerSetOfEmptySet.add (Arrays.asList (új logikai [n])); return powerSetOfEmptySet; } Beállítás powerSetSubset = recursivePowerSetBinaryRepresentation (idx + 1, n); Készlet powerSet = új HashSet (); mert (List s: powerSetSubset) {List subSetIdxExclusive = new ArrayList (s); subSetIdxExclusive.set (idx, hamis); powerSet.add (subSetIdxExclusive); List subSetIdxInclusive = new ArrayList (s); subSetIdxInclusive.set (idx, true); powerSet.add (subSetIdxInclusive); } return powerSet; }

5.5. Iterálni keresztül [0, 2n)

Most van egy szép optimalizálás, amelyet megtehetünk a bináris ábrázolással. Ha megnézzük, láthatjuk, hogy minden sor egyenértékű egy szám bináris formátumával [0, 2n].

Tehát, ha iterálunk a számokból 0 nak nek 2n, átalakíthatjuk az indexet binárisra, és felhasználhatjuk az egyes részhalmazok logikai ábrázolásának létrehozására:

privát lista iterativePowerSetByLoopOverNumbers (int n) {Lista powerSet = new ArrayList (); for (int i = 0; i <(1 << n); i ++) {Lista részhalmaz = új tömblista (n); for (int j = 0; j <n; j ++) részhalmaz.add ((((1 <0); powerSet.add (részhalmaz);} return powerSet;}

5.6. Minimális változás az alcsoportokban szürke kód szerint

Most, ha meghatározunk bármilyen bijektív függvényt a hosszúság bináris ábrázolásából n számra be [0, 2n), tetszőleges sorrendben generálhatunk részhalmazokat.

A szürke kód egy jól ismert függvény, amelyet a számok bináris reprezentációinak előállítására használnak, így az egymást követő számok bináris ábrázolása csak egy bittel tér el (még az utolsó és az első szám különbsége is egy).

Így ezt egy kicsit tovább optimalizálhatjuk:

privát lista iterativePowerSetByLoopOverNumbersWithGrayCodeOrder (int n) {Lista powerSet = new ArrayList (); for (int i = 0; i <(1 << n); i ++) {Lista részhalmaz = új tömblista (n); mert (int j = 0; j > 1); részhalmaz.add ((((1 <0);} powerSet.add (részhalmaz);} return powerSet;}

6. Lusta betöltés

Az energiaellátás helyhasználatának minimalizálása érdekében, ami O (2n), felhasználhatjuk a Iterátor felület minden részhalmaz és minden alkészlet minden elemének lustán történő lekéréséhez.

6.1. ListIterator

Először is, hogy iterálni lehessen 0 nak nek 2n, kellene egy különlegességünk Iterátor amely ezen a tartományon keresztül hurkol, de előzetesen nem fogyasztja el a teljes tartományt.

A probléma megoldásához két változót fogunk használni; egyet a mérethez, ami 2n, és egy másik az aktuális részhalmaz indexhez. A mi hasNext () funkció ellenőrizni fogja pozíció kevesebb mint méret:

absztrakt osztály ListIterator megvalósítja az Iterator {védett int helyzet = 0; privát int méret; public ListIterator (int méret) {this.size = méret; } @Orride public boolean hasNext () {return position <size; }}

És a mi következő() függvény adja vissza az áram részhalmazát pozíció és növeli a pozíció egyenként:

@Orride public Set next () {return new Subset (map, reverseMap, position ++); }

6.2. Részhalmaz

Lusta terhelés Részhalmaz, meghatározunk egy osztályt, amely kiterjed AbstractSet, és felülírjuk néhány funkcióját.

Az összes bit hurkolásával 1 a befogadóban maszk (vagy pozíció) a Részhalmaz, megvalósíthatjuk a Iterátor és egyéb módszerek AbstractSet.

Például a méret() a száma 1s a befogadóban maszk:

@Orride public int size () {return Integer.bitCount (mask); }

És a tartalmaz () függvény csak az, hogy az adott bit a maszk van 1 vagy nem:

A @Override public boolean tartalmazza a (@Nullable Object o) {Egész szám index = map.get (o); visszatérési index! = null && (maszk & (1 << index))! = 0; }

Egy másik változót használunk - paliekSetBits - módosítani, amikor lekérjük a megfelelő elemét abban a részhalmazban, amelyre azt a bitet megváltoztatjuk 0. Aztán a hasNext () ellenőrzi, hogy paliekSetBits nem nulla (vagyis legalább egy bitje van, értéke: 1):

@Orride public boolean hasNext () {return leftSetBits return = 0; }

És a következő() függvény használja a jobb oldali 1 ban,-ben paliekSetBits, majd átalakítja 0, és visszaadja a megfelelő elemet is:

@ A nyilvános E felülírása következő () {int index = Egész szám.SzámOfTrailingZérók (maradékSetBits); if (index == 32) {dobjon új NoSuchElementException (); } maradtSetBits & = ~ (1 << index); return reverseMap.get (index); }

6.3. PowerSet

Lusta teher PowerSet osztályra van szükségünk, amely kiterjed AbstractSet.

A méret() függvény egyszerűen 2 a halmaz méretének erejéig:

@Orride public int size () {return (1 << this.set.size ()); }

Mivel a teljesítménykészlet a bemeneti készlet összes lehetséges részhalmazát tartalmazza, így tartalmazza (o objektum) a funkció ellenőrzi, hogy a tárgy o léteznek a reverseMap (vagy a bemeneti készletben):

@ A nyilvános logikai érték felülbírálása tartalmaz (@Nullable Object obj) {if (obj példánya Set) {Set set = (Set) obj; return reverseMap.containsAll (készlet); } return false; }

Egy adott egyenlőségének ellenőrzése Tárgy ezzel az osztállyal csak a bemenetet ellenőrizhetjük készlet egyenlő az adott Tárgy:

@Orride public boolean egyenlő (@Nullable Object obj) {if (PowerSet obj instanceof) {PowerSet that = (PowerSet) obj; return set.equals (az a halmaz); } adja vissza a szuper.egyenlőséget (obj); }

A iterátor () függvény adja vissza a ListIterator amit már meghatároztunk:

@Orride public Iterator iterator () {return new ListIterator(this.size ()) {@Orride public Set next () {return new Subset (map, reverseMap, position ++); }}; }

A guavai könyvtár használja ezt a lusta terhelésű ötletet és ezeket PowerSet és Részhalmaz a guavai könyvtár egyenértékű megvalósításai.

További információért ellenőrizze a forráskódot és a dokumentációt.

Továbbá, ha párhuzamosan akarunk műveletet végezni a részhalmazok felett PowerSet, hívhatunk Részhalmaz a különböző értékeknél a ThreadPool.

7. Összegzés

Összefoglalva, először azt tanulmányoztuk, hogy mi a hatalomkészlet. Ezután a Guava Library használatával generáltuk. Ezt követően megvizsgáltuk a megközelítést és annak megvalósításának módját, valamint azt, hogy miként írhatunk rá egység tesztet.

Végül felhasználtuk a Iterátor interfész az alhalmazok és azok belső elemeinek generációs terének optimalizálására.

Mint mindig, a forráskód elérhető a GitHubon.