Dobivanje Power Set-a skupa u Javi
1. Uvod
U ovom uputstvu proučit ćemo postupak generiranja skupa snage određenog skupa u Javi.
Kao kratki podsjetnik, za svaki skup veličina n, postoji sklop snage veličine 2n. Naučit ćemo kako to dobiti koristeći razne tehnike.
2. Definicija sklopa napajanja
Skup snage određenog skupa S je skup svih podskupova S, uključujući S sebe i prazan skup.
Na primjer, za zadani skup:
{"JABUKA", "NARANČASTA", "MANGO"}postavljena snaga je:
{{}, {"APPLE"}, {"ORANGE"}, {"APPLE", "ORANGE"}, {"MANGO"}, {"APPLE", "MANGO"}, {"ORANGE", "MANGO" }, {"JABUKA", "NARANČASTA", "MANGO"}}Kako je to također skup podskupova, redoslijed njegovih unutarnjih podskupova nije važan i oni se mogu pojaviti u bilo kojem redoslijedu:
{{}, {"MANGO"}, {"ORANGE"}, {"ORANGE", "MANGO"}, {"APPLE"}, {"APPLE", "MANGO"}, {"APPLE", "ORANGE" }, {"JABUKA", "NARANČASTA", "MANGO"}}3. Knjižnica Guava
Biblioteka Google Guava ima nekoliko korisnih Postavi uslužne programe, poput postavljenog napajanja. Stoga ga lako možemo koristiti i za dobivanje skupa snage datog skupa:
@Test javna praznina givenSet_WhenGuavaLibraryGeneratePowerSet_ThenItContainsAllSubsets () {ImmutableSet set = ImmutableSet.of ("APPLE", "ORANGE", "MANGO"); Postavi powerSet = Sets.powerSet (set); 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")) ; } Guava powerSet interno djeluje preko Iterator sučelje na način kada se traži sljedeći podskup, podskup se izračunava i vraća. Dakle, složenost prostora svedena je na Na) umjesto O (2n).
Ali, kako Guava to postiže?
4. Pristup generiranju napajanja
4.1. Algoritam
Razmotrimo sada moguće korake za stvaranje algoritma za ovu operaciju.
Skup snage praznog skupa je {{}} u kojem sadrži samo jedan prazan skup, pa je to naš najjednostavniji slučaj.
Za svaki set S osim praznog skupa, prvo izdvajamo jedan element i imenujemo ga - element. Zatim, za ostale elemente skupa subsetWithoutElement, izračunavamo njihov set snage rekurzivno - i imenujemo ga slično powerSetSubsetWithoutElement. Zatim, dodavanjem izvađenog element na sve skupove powerSetSubsetWithoutElement, shvaćamo powerSetSubsetWithElement.
Sada, snaga postavljena S je unija a powerSetSubsetWithoutElement i a powerSetSubsetWithElement:
Pogledajmo primjer steka rekurzivnog skupa snage za zadani skup {„JABUKA“, „NARANČASTA“, „MANGO“}.
Da bismo poboljšali čitljivost slike, koristimo kratke oblike imena: Str označava funkciju postavljene snage i "A", "O", "M" su kratki oblici „JABUKA“, „NARANČASTA“, i "MANGO", odnosno:
4.2. Provedba
Dakle, prvo, napišite Java kôd za izdvajanje jednog elementa i uzmite preostale podskupine:
T element = set.iterator (). Next (); Postavi subsetWithoutElement = novi HashSet (); za (T s: set) {if (! s.equals (element)) {subsetWithoutElement.add (s); }}Tada ćemo htjeti dobiti powerset od subsetWithoutElement:
Postavi powersetSubSetWithoutElement = rekurzivniPowerSet (subsetWithoutElement); Dalje, taj powerset moramo dodati natrag u izvornik:
Postavi powersetSubSetWithElement = novi HashSet (); for (Set subsetWithoutElement: powerSetSubSetWithoutElement) {Set subsetWithElement = new HashSet (subsetWithoutElement); subsetWithElement.add (element); powerSetSubSetWithElement.add (subsetWithElement); } Napokon unija powerSetSubSetWithoutElement i powerSetSubSetWithElement je set snage datog ulaznog skupa:
Postavi powerSet = novi HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); Ako složimo sve naše isječke koda, možemo vidjeti konačni proizvod:
javni Set rekurzivniPowerSet (Postavi skup) {if (set.isEmpty ()) {Postavi ret = novi HashSet (); ret.add (set); povratak ret; } T element = set.iterator (). Next (); Postavi subSetWithoutElement = getSubSetWithoutElement (set, element); Postavi powerSetSubSetWithoutElement = rekurzivniPowerSet (subSetWithoutElement); Postavi powerSetSubSetWithElement = addElementToAll (powerSetSubSetWithoutElement, element); Postavi powerSet = novi HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); povrat snage; } 4.3. Napomene za jedinične testove
Sada testirajmo. Ovdje imamo nekoliko kriterija za potvrdu:
- Prvo provjeravamo veličinu postavljene snage i ona mora biti 2n za skup veličine n.
- Tada će se svaki element pojaviti samo jednom u podskupu i 2n-1 različite podskupine.
- Napokon, svaka se podskupina mora pojaviti jednom.
Ako su svi ti uvjeti prošli, možemo biti sigurni da naša funkcija funkcionira. Sad, otkad koristimo Postavi, već znamo da nema ponavljanja. U tom slučaju trebamo samo provjeriti veličinu skupa snage i broj pojavljivanja svakog elementa u podskupinama.
Da bismo provjerili veličinu sklopa napajanja možemo koristiti:
MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ())));I da provjerite broj pojavljivanja svakog elementa:
Brojač mapa = novi HashMap (); za (Postavi podskup: powerSet) {za (Naziv niza: podskup) {int num = counter.getOrDefault (ime, 0); counter.put (ime, broj + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ()));Konačno, ako sve možemo spojiti u jedan jedinični test:
@Test javna praznina givenSet_WhenPowerSetIsCalculated_ThenItContainsAllSubsets () {Set set = RandomSetOfStringGenerator.generateRandomSet (); Postavi powerSet = novi PowerSet (). rekurzivniPowerSet (postavljen); MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ()))); Brojač mapa = novi HashMap (); za (Postavi podskup: powerSet) {za (Naziv niza: podskup) {int num = counter.getOrDefault (ime, 0); counter.put (ime, broj + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ())); } 5. Optimizacija
U ovom ćemo odjeljku pokušati smanjiti prostor i smanjiti broj unutarnjih operacija za izračunavanje postavljene snage na optimalan način.
5.1. Struktura podataka
Kao što možemo vidjeti u danom pristupu, trebamo puno oduzimanja u rekurzivnom pozivu, koji troši veliku količinu vremena i memorije.
Umjesto toga, svaki skup ili podskup možemo preslikati na neke druge pojmove kako bismo smanjili broj operacija.
Prvo, svakom objektu u danom skupu moramo dodijeliti sve veći broj počevši od 0 S što znači da radimo s uređenim popisom brojeva.
Na primjer za zadani skup {„JABUKA“, „NARANČASTA“, „MANGO“} dobivamo:
"JABUKA" -> 0
“NARANČASTA” ->
“MANGO” -> 2
Dakle, od sada, umjesto da generiramo podskupine S, generiramo ih za poredani popis [0, 1, 2], a kako je naređeno, oduzimanja možemo simulirati početnim indeksom.
Na primjer, ako je početni indeks 1, to znači da generiramo skup snaga od [1,2].
Da bismo dohvatili mapirani ID iz objekta i obrnuto, pohranjujemo obje strane mapiranja. Koristeći naš primjer, pohranjujemo oboje ("MANGO" -> 2) i (2 -> „MANGO“). Kako je mapiranje brojeva počelo od nule, tako i za obrnutu kartu možemo koristiti jednostavni niz za dohvaćanje odgovarajućeg objekta.
Jedna od mogućih implementacija ove funkcije bila bi:
karta privatne mape = novi HashMap (); privatni popis reverseMap = novi ArrayList (); private void initializeMap (zbirka kolekcije) {int mapId = 0; for (T c: collection) {map.put (c, mapId ++); reverseMap.add (c); }}Sada, za predstavljanje podskupina, postoje dvije dobro poznate ideje:
- Zastupljenost indeksa
- Binarni prikaz
5.2. Zastupljenost indeksa
Svaka podskupina predstavljena je indeksom svojih vrijednosti. Na primjer, indeksiranje datog skupa {„JABUKA“, „NARANČASTA“, „MANGO“} bilo bi:
{{}} -> {} [0] -> {"JABUKA"} [1] -> {"NARANČASTA"} [0,1] -> {"JABUKA", "NARANČASTA}} [2] -> {" MANGO "} [0,2] -> {" JABUKA "," MANGO "} [1,2] -> {" NARANČASTO, "MANGO"} [0,1,2] -> {"JABUKA", " NARANČASTA "," MANGO "}}Dakle, dotični skup možemo dohvatiti iz podskupina indeksa s danim preslikavanjem:
privatni Set unMapIndex (Postavi setovi) {Set ret = novi HashSet (); za (Set s: skupova) {HashSet podskup = novi HashSet (); za (Integer i: s) {subset.add (reverseMap.get (i)); } ret.add (podskup); } povratak ret; } 5.3. Binarno predstavljanje
Ili, možemo predstaviti svaki podskup pomoću binarnog. Ako u ovom podskupinu postoji element stvarnog skupa, njegova je vrijednost 1; inače je 0.
Za naš primjer voća postavljena bi snaga bila:
{[0,0,0] -> {} [1,0,0] -> {"JABUKA"} [0,1,0] -> {"NARANČASTA}} [1,1,0] -> { "JABUKA", "NARANČASTA"} [0,0,1] -> {"MANGO"} [1,0,1] -> {"JABUKA", "MANGO"} [0,1,1] -> { "NARANČASTA", "MANGO"} [1,1,1] -> {"JABUKA", "NARANČASTA", "MANGO"}}Dakle, možemo dohvatiti odgovarajući skup iz binarnog podskupa s danim preslikavanjem:
privatni Set unMapBinary (Zbirka setovi) {Set ret = novi HashSet (); za (Popis s: skupova) {HashSet podskup = novi HashSet (); for (int i = 0; i <s.size (); i ++) {if (s.get (i)) {subset.add (reverseMap.get (i)); }} ret.add (podskup); } povratak ret; }
5.4. Implementacija rekurzivnog algoritma
U ovom ćemo koraku pokušati implementirati prethodni kôd koristeći obje podatkovne strukture.
Prije pozivanja jedne od ovih funkcija, trebamo nazvati initializeMap metoda za dobivanje poredanog popisa. Također, nakon stvaranja naše strukture podataka, trebamo nazvati odgovarajuće poništi kartu funkcija za dohvaćanje stvarnih objekata:
javni Set rekurzivnaPowerSetIndexRepresentation (Skup zbirki) {initializeMap (set); Postavi powerSetIndices = rekurzivnaPowerSetIndexRepresentation (0, set.size ()); vrati unMapIndex (powerSetIndices); } Pa, okušajmo se u predstavljanju indeksa:
privatni Set rekurzivnaPowerSetIndexRepresentation (int idx, int n) {if (idx == n) {Set prazno = novi HashSet (); empty.add (novi HashSet ()); povratak prazan; } Postavi powerSetSubset = rekurzivnaPowerSetIndexRepresentation (idx + 1, n); Postavi powerSet = novi HashSet (powerSetSubset); za (Set s: powerSetSubset) {HashSet subSetIdxInclusive = novi HashSet (s); subSetIdxInclusive.add (idx); powerSet.add (subSetIdxInclusive); } return powerSet; } Pogledajmo sada binarni pristup:
privatni Set rekurzivnaPowerSetBinaryRepresentation (int idx, int n) {if (idx == n) {Set powerSetOfEmptySet = novi HashSet (); powerSetOfEmptySet.add (Arrays.asList (novo logičko [n])); vrati powerSetOfEmptySet; } Postavi powerSetSubset = rekurzivnaPowerSetBinaryRepresentation (idx + 1, n); Postavi powerSet = novi HashSet (); za (Popis s: powerSetSubset) {Popis subSetIdxExclusive = novi ArrayList (s); subSetIdxExclusive.set (idx, false); powerSet.add (subSetIdxExclusive); Popis subSetIdxInclusive = novi ArrayList (s); subSetIdxInclusive.set (idx, true); powerSet.add (subSetIdxInclusive); } return powerSet; }
5.5. Ponavljajte [0, 2n)
Sada postoji lijepa optimizacija koju možemo učiniti s binarnim prikazom. Ako ga pogledamo, možemo vidjeti da je svaki redak ekvivalentan binarnom formatu broja u [0,2 n).
Dakle, ako ponovimo brojeve iz 0 do 2n, taj indeks možemo pretvoriti u binarni i pomoću njega stvoriti logički prikaz svakog podskupa:
privatni Popis iterativePowerSetByLoopOverNumbers (int n) {Popis powerSet = novi ArrayList (); for (int i = 0; i <(1 << n); i ++) {Popis podskupina = novi ArrayList (n); za (int j = 0; j <n; j ++) podskup.add (((1 <0); powerSet.add (podskup);} return powerSet;}
5.6. Podskupovi minimalnih promjena prema sivom kodu
Sada, ako definiramo bilo koju bijektivnu funkciju iz binarnog prikaza duljine n na broj u [0, 2n), možemo generirati podskupine u bilo kojem redoslijedu koji želimo.
Sivi kod dobro je poznata funkcija koja se koristi za generiranje binarnih prikaza brojeva tako da se binarni prikaz uzastopnih brojeva razlikuje samo za jedan bit (čak je i razlika posljednjeg i prvog broja jedna).
Stoga ovo možemo optimizirati samo malo dalje:
privatni Popis iterativePowerSetByLoopOverNumbersWithGrayCodeOrder (int n) {Popis powerSet = novi ArrayList (); for (int i = 0; i <(1 << n); i ++) {Popis podskupina = novi ArrayList (n); za (int j = 0; j > 1); subset.add (((1 <0);} powerSet.add (subset);} return powerSet;}
6. Lijeno utovar
Da bi se smanjila upotreba prostora postavljene snage, što je O (2n), možemo koristiti Iterator sučelje za lijeno dohvaćanje svake podskupine, a također i svakog elementa u svakoj podskupini.
6.1. ListIterator
Prvo, da biste mogli ponoviti 0 do 2n, trebali bismo imati poseban Iterator koji se petlja preko ovog raspona, ali prethodno ne troši cijeli raspon.
Da bismo riješili taj problem, upotrijebit ćemo dvije varijable; jedan za veličinu, što je 2ni još jedan za trenutni indeks podskupa. Naše hasNext () funkcija će to provjeriti položaj je manje od veličina:
apstraktna klasa ListIterator implementira Iterator {zaštićen int položaj = 0; privatna int veličina; javni ListIterator (int veličina) {this.size = size; } @Override public boolean hasNext () {return position <size; }}I naše Sljedeći() funkcija vraća podskup trenutne vrijednosti položaj a povećava vrijednost položaj po jedan:
@Override public Set next () {return new Podskup (map, reverseMap, position ++); }6.2. Podskup
Da imam lijeni teret Podskup, definiramo klasu koja se proteže Skup sažetakai nadjačavamo neke od njegovih funkcija.
Prevlačenjem svih bitova koji jesu 1 u primanju maska (ili položaj) od Podskup, možemo implementirati Iterator i druge metode u Skup sažetaka.
Na primjer, veličina() je broj 1s u primanju maska:
@Override public int size () {return Integer.bitCount (maska); }I sadrži () funkcija je samo je li odgovarajući bit u maska je 1 ili ne:
@Override public boolean sadrži (@Nullable Object o) {Integer index = map.get (o); indeks povrata! = null && (maska & (1 << indeks))! = 0; }Koristimo drugu varijablu - preostaliSetBits - da ga modificiramo kad god dohvatimo njegov odgovarajući element u podskupu kojem promijenimo taj bit 0. Onda hasNext () provjerava je li preostaliSetBits nije nula (tj. ima barem jedan bit s vrijednošću 1):
@Override public boolean hasNext () {return residSetBits! = 0; }I Sljedeći() funkcija koristi najdesnije 1 u preostaliSetBits, a zatim ga pretvara u 0, a također vraća odgovarajući element:
@Override public E next () {int index = Integer.numberOfTrailingZeros (preostaliSetBits); if (index == 32) {baciti novi NoSuchElementException (); } preostaliSetBits & = ~ (1 << indeks); vrati returnMap.get (indeks); }6.3. PowerSet
Da imam lijeno opterećenje PowerSet klase, trebamo klasu koja se proteže Skup sažetaka
The veličina() funkcija je jednostavno 2 prema veličini skupa:
@Preuzmi javnu int veličinu () {return (1 << this.set.size ()); }Kako će skup snage sadržavati sve moguće podskupove ulaznog skupa, tako sadrži (objekt o) funkcija provjerava jesu li svi elementi objekt o postoje u reverseMap (ili u ulaznom skupu):
@Override public boolean sadrži (@Nullable Object obj) {if (obj instanceof Set) {Set set = (Set) obj; return returnMap.containsAll (set); } return false; }Provjeriti jednakost zadanog Objekt s ovom klasom možemo samo provjeriti je li ulaz postavljen jednak je zadanom Objekt:
@Override public boolean equals (@Nullable Object obj) {if (obj instanceof PowerSet) {PowerSet that = (PowerSet) obj; vrati set.equals (that.set); } return super.equals (obj); }The iterator () funkcija vraća primjerak ListIterator koje smo već definirali:
@Preuzmi javni iterator iterator () {vratiti novi ListIterator(this.size ()) {@Override public Set next () {return new Podskup (map, reverseMap, position ++); }}; } Knjižnica Guava koristi ovu ideju lijenog opterećenja i ove PowerSet i Podskup su ekvivalentne implementacije knjižnice Guava.
Za više informacija provjerite njihov izvorni kod i dokumentaciju.
Nadalje, ako želimo raditi paralelnu operaciju nad podskupovima u PowerSet, možemo nazvati Podskup za različite vrijednosti u a ThreadPool.
7. Sažetak
Da sumiramo, prvo smo proučavali što je skup snaga. Zatim smo ga generirali pomoću knjižnice Guava. Nakon toga proučavali smo pristup i kako bismo ga trebali implementirati, kao i kako za njega napisati jedinični test.
Napokon smo iskoristili Iterator sučelje za optimizaciju prostora generiranja podskupova i također njihovih unutarnjih elemenata.
Kao i uvijek izvorni kod dostupan je na GitHub-u.
