Skaffe et Power Set of a Set i Java
1. Introduksjon
I denne opplæringen studerer vi prosessen med å generere et kraftsett for et gitt sett i Java.
Som en rask påminnelse, for hvert sett med størrelser n, det er et strømsett av størrelse 2n. Vi lærer hvordan du får tak i det ved hjelp av forskjellige teknikker.
2. Definisjon av et kraftsett
Kraftsettet til et gitt sett S er settet med alle delmengder av S, gjelder også S seg selv og det tomme settet.
For eksempel for et gitt sett:
{"APPLE", "ORANGE", "MANGO"}strømsettet er:
{{}, {"APPLE"}, {"ORANGE"}, {"APPLE", "ORANGE"}, {"MANGO"}, {"APPLE", "MANGO"}, {"ORANGE", "MANGO" }, {"APPLE", "ORANGE", "MANGO"}}Siden det også er et sett med delmengder, er ikke rekkefølgen på dets interne delmengder viktig, og de kan vises i hvilken som helst rekkefølge:
{{}, {"MANGO"}, {"ORANGE"}, {"ORANGE", "MANGO"}, {"APPLE"}, {"APPLE", "MANGO"}, {"APPLE", "ORANGE" }, {"APPLE", "ORANGE", "MANGO"}}3. Guava-biblioteket
Google Guava-biblioteket har noe nyttig Sett verktøy, for eksempel strømforsyningen. Dermed kan vi enkelt bruke den til å få kraften til det gitte settet også:
@Test offentlig ugyldighet givenSet_WhenGuavaLibraryGeneratePowerSet_ThenItContainsAllSubsets () {ImmutableSet set = ImmutableSet.of ("APPLE", "ORANGE", "MANGO"); Sett powerSet = Sets.powerSet (sett); 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 internt opererer over Iterator grensesnitt på den måten når neste delsett blir bedt om, blir delsettet beregnet og returnert. Så er plasskompleksiteten redusert til På) i stedet for O (2n).
Men hvordan oppnår Guava dette?
4. Power Approach Generation Approach
4.1. Algoritme
La oss nå diskutere de mulige trinnene for å lage en algoritme for denne operasjonen.
Kraftsettet til et tomt sett er {{}} der den bare inneholder ett tomt sett, så det er vårt enkleste tilfelle.
For hvert sett S annet enn det tomme settet, trekker vi først ut ett element og navngir det - element. Så, for resten av elementene i et sett delsettWithoutElement, vi beregner kraftsettet rekursivt - og kaller det noe sånt som powerSetSubsetWithoutElement. Deretter, ved å legge til det ekstraherte element til alle sett i powerSetSubsetWithoutElement, vi får powerSetSubsetWithElement.
Nå er strømmen satt S er foreningen av en powerSetSubsetWithoutElement og en powerSetSubsetWithElement:
La oss se et eksempel på den rekursive bunnsettbunken for det gitte settet {“APPLE”, “ORANGE”, “MANGO”}.
For å forbedre bildets lesbarhet bruker vi korte navneformer: P betyr strøminnstillingsfunksjon og “A”, “O”, “M” er korte former for “APPLE”, “ORANGE”, og “MANGO”, henholdsvis:
4.2. Gjennomføring
Så, først, la oss skrive Java-koden for å trekke ut ett element og få de gjenværende delmengdene:
T element = set.iterator (). Neste (); Set subsetWithoutElement = new HashSet (); for (T s: set) {if (! s.equals (element)) {subsetWithoutElement.add (s); }}Vi vil da få kraften til delsettWithoutElement:
Sett powersetSubSetWithoutElement = recursivePowerSet (subsetWithoutElement); Deretter må vi legge den kraftforsamlingen tilbake i originalen:
Sett powersetSubSetWithElement = ny HashSet (); for (Set subsetWithoutElement: powerSetSubSetWithoutElement) {Set subsetWithElement = new HashSet (subsetWithoutElement); subsetWithElement.add (element); powerSetSubSetWithElement.add (subsetWithElement); } Endelig foreningen av powerSetSubSetWithoutElement og powerSetSubSetWithElement er kraftsettet til det gitte inngangssettet:
Sett powerSet = nytt HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); Hvis vi setter sammen alle kodebitene våre, kan vi se vårt endelige produkt:
offentlig sett recursivePowerSet (Set set) {if (set.isEmpty ()) {Set ret = ny HashSet (); ret.add (sett); retur ret; } T element = set.iterator (). Neste (); Sett subSetWithoutElement = getSubSetWithoutElement (sett, element); Sett powerSetSubSetWithoutElement = rekursivPowerSet (subSetWithoutElement); Sett powerSetSubSetWithElement = addElementToAll (powerSetSubSetWithoutElement, element); Sett powerSet = nytt HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); return powerSet; } 4.3. Merknader for enhetstester
La oss nå teste. Vi har litt kriterier her for å bekrefte:
- Først sjekker vi størrelsen på strømsettet og det må være 2n for et sett med størrelse n.
- Deretter vil hvert element bare forekomme en gang i en delmengde og 2n-1 forskjellige delmengder.
- Til slutt må hvert delsett vises en gang.
Hvis alle disse forholdene passerte, kan vi være sikre på at funksjonen vår fungerer. Nå, siden vi har brukt Sett, vi vet allerede at det ikke er noen repetisjon. I så fall trenger vi bare å sjekke størrelsen på strømsettet, og antall forekomster av hvert element i delsettene.
For å sjekke størrelsen på kraftsettet kan vi bruke:
MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ())));Og for å sjekke antall forekomster av hvert element:
Kartteller = nytt HashMap (); for (Set subset: powerSet) {for (String name: subset) {int num = counter.getOrDefault (name, 0); counter.put (navn, num + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ()));Til slutt, hvis vi kan sette alt sammen i en enhetstest:
@Test offentlig ugyldighet givenSet_WhenPowerSetIsCalculated_ThenItContainsAllSubsets () {Set set = RandomSetOfStringGenerator.generateRandomSet (); Sett powerSet = ny PowerSet (). rekursivPowerSet (sett); MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ())); Kartteller = nytt HashMap (); for (Set subset: powerSet) {for (String name: subset) {int num = counter.getOrDefault (name, 0); counter.put (navn, num + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ())); } 5. Optimalisering
I denne delen vil vi prøve å minimere plassen og redusere antall interne operasjoner for å beregne effektinnstillingen på en optimal måte.
5.1. Data struktur
Som vi kan se i den gitte tilnærmingen, trenger vi mange subtraksjoner i det rekursive anropet, som bruker mye tid og minne.
I stedet kan vi kartlegge hvert sett eller delmengde til noen andre forestillinger for å redusere antall operasjoner.
Først må vi tilordne et økende antall fra 0 til hvert objekt i det gitte settet S noe som betyr at vi jobber med en ordnet nummerliste.
For eksempel for det gitte settet {“APPLE”, “ORANGE”, “MANGO”} vi får:
“APPLE” -> 0
“ORANGE” ->
“MANGO” -> 2
Så fra nå av, i stedet for å generere delmengder av Sgenererer vi dem for den ordnede listen over [0, 1, 2], og når den er bestilt, kan vi simulere subtraksjoner med en startindeks.
For eksempel, hvis startindeksen er 1, betyr det at vi genererer effektsettet [1,2].
For å hente kartlagt ID fra objektet og omvendt lagrer vi begge sider av kartleggingen. Ved hjelp av eksemplet vårt lagrer vi begge deler (“MANGO” -> 2) og (2 -> “MANGO”). Når kartleggingen av tall startet fra null, kan vi bruke en enkel matrise for å hente det respektive objektet for det omvendte kartet der.
En av de mulige implementeringene av denne funksjonen vil være:
privat kartkart = nytt HashMap (); privat liste reverseMap = ny ArrayList (); private void initializeMap (Collection collection) {int mapId = 0; for (T c: samling) {map.put (c, mapId ++); reverseMap.add (c); }}For å representere delmengder er det to kjente ideer:
- Indeksrepresentasjon
- Binær representasjon
5.2. Indeksrepresentasjon
Hver delmengde er representert med indeksen over verdiene. For eksempel indekskartleggingen av det gitte settet {“APPLE”, “ORANGE”, “MANGO”} ville vært:
{{} -> {} [0] -> {"APPLE"} [1] -> {"ORANGE"} [0,1] -> {"APPLE", "ORANGE"} [2] -> {" MANGO "} [0,2] -> {" APPLE "," MANGO "} [1,2] -> {" ORANGE "," MANGO "} [0,1,2] -> {" APPLE "," ORANGE "," MANGO "}}Så vi kan hente det respektive settet fra en delmengde av indekser med den gitte kartleggingen:
privat sett unMapIndex (sett sett) {Sett ret = ny HashSet (); for (Set s: sets) {HashSet subset = new HashSet (); for (Heltall i: s) {subset.add (reverseMap.get (i)); } ret.add (delmengde); } returnere ret; } 5.3. Binær representasjon
Eller vi kan representere hvert delsett ved hjelp av binær. Hvis et element av det faktiske settet eksisterer i dette delsettet, er dets respektive verdi 1; ellers er det 0.
For vårt frukteksempel, ville maktsettet være:
{[0,0,0] -> {} [1,0,0] -> {"APPLE"} [0,1,0] -> {"ORANGE"} [1,1,0] -> { "APPLE", "ORANGE"} [0,0,1] -> {"MANGO"} [1,0,1] -> {"APPLE", "MANGO"} [0,1,1] -> { "ORANGE", "MANGO"} [1,1,1] -> {"APPLE", "ORANGE", "MANGO"}}Så vi kan hente det aktuelle settet fra en binær delmengde med den gitte kartleggingen:
privat sett unMapBinary (samling sett) {Sett ret = ny HashSet (); for (List s: sets) {HashSet subset = new HashSet (); for (int i = 0; i <s.size (); i ++) {if (s.get (i)) {subset.add (reverseMap.get (i)); }} ret.add (delmengde); } returnere ret; }
5.4. Rekursiv algoritmeimplementering
I dette trinnet vil vi prøve å implementere den forrige koden ved hjelp av begge datastrukturer.
Før vi ringer til en av disse funksjonene, må vi ringe initializeMap metode for å få den bestilte listen. Etter å ha opprettet datastrukturen vår, må vi også ringe den respektive unMap funksjon for å hente de faktiske objektene:
offentlig sett recursivePowerSetIndexRepresentation (Collection set) {initializeMap (set); Sett powerSetIndices = recursivePowerSetIndexRepresentation (0, set.size ()); returner unMapIndex (powerSetIndices); } Så la oss prøve oss på indeksrepresentasjonen:
privat sett recursivePowerSetIndexRepresentation (int idx, int n) {if (idx == n) {Set tom = ny HashSet (); empty.add (nytt HashSet ()); returner tom; } Sett powerSetSubset = rekursivPowerSetIndexRepresentation (idx + 1, n); Sett powerSet = nytt HashSet (powerSetSubset); for (Set s: powerSetSubset) {HashSet subSetIdxInclusive = new HashSet (s); subSetIdxInclusive.add (idx); powerSet.add (subSetIdxInclusive); } returner powerSet; } La oss nå se den binære tilnærmingen:
privat sett recursivePowerSetBinaryRepresentation (int idx, int n) {if (idx == n) {Set powerSetOfEmptySet = ny HashSet (); powerSetOfEmptySet.add (Arrays.asList (ny boolsk [n])); return powerSetOfEmptySet; } Sett powerSetSubset = rekursivPowerSetBinaryRepresentation (idx + 1, n); Sett powerSet = nytt HashSet (); for (List s: powerSetSubset) {List subSetIdxExclusive = new ArrayList (s); subSetIdxExclusive.set (idx, false); powerSet.add (subSetIdxExclusive); List subSetIdxInclusive = new ArrayList (s); subSetIdxInclusive.set (idx, true); powerSet.add (subSetIdxInclusive); } returner powerSet; }
5.5. Iterere gjennom [0, 2n)
Nå er det en fin optimalisering vi kan gjøre med den binære representasjonen. Hvis vi ser på det, kan vi se at hver rad tilsvarer det binære formatet til et tall i [0, 2n).
Så hvis vi gjentar oss gjennom tall fra 0 til 2n, kan vi konvertere den indeksen til binær, og bruke den til å lage en boolsk representasjon av hvert delsett:
privat liste iterativePowerSetByLoopOverNumbers (int n) {Liste powerSet = ny ArrayList (); for (int i = 0; i <(1 << n); i ++) {List subset = new ArrayList (n); for (int j = 0; j <n; j ++) delsett.add (((1 <0); powerSet.add (delsett);} returner powerSet;}
5.6. Delsett med minimale endringer etter grå kode
Nå, hvis vi definerer en hvilken som helst bijektiv funksjon fra binær representasjon av lengde n til et tall i [0, 2n), kan vi generere delsett i hvilken rekkefølge vi ønsker.
Grå kode er en velkjent funksjon som brukes til å generere binære representasjoner av tall slik at den binære representasjonen av påfølgende tall bare avviker med en bit (selv forskjellen på siste og første tall er en).
Vi kan dermed optimalisere dette bare litt lenger:
privat liste iterativePowerSetByLoopOverNumbersWithGrayCodeOrder (int n) {List powerSet = ny ArrayList (); for (int i = 0; i <(1 << n); i ++) {List subset = new ArrayList (n); for (int j = 0; j > 1); subset.add (((1 <0);} powerSet.add (subset);} return powerSet;}
6. Lazy Loading
For å minimere plassforbruket til strømforsyningen, som er O (2n), kan vi bruke Iterator grensesnitt for å hente hvert delsett, og også hvert element i hvert delsett lat.
6.1. ListIterator
For det første å kunne gjenta fra 0 til 2n, vi burde ha en spesiell Iterator som sløyfer over dette området, men ikke forbruker hele spekteret på forhånd.
For å løse dette problemet bruker vi to variabler; en for størrelsen, som er 2n, og en annen for gjeldende delsettindeks. Våre hasNext () funksjon vil sjekke det posisjon er mindre enn størrelse:
abstrakt klasse ListIterator implementerer Iterator {beskyttet int posisjon = 0; privat int størrelse; offentlig ListIterator (int størrelse) {this.size = størrelse; } @Override offentlig boolsk hasNext () {returposisjon <størrelse; }}Og vår neste () funksjonen returnerer delsettet for gjeldende posisjon og øker verdien av posisjon av en:
@ Override public Set next () {return new Subset (map, reverseMap, position ++); }6.2. Delsett
Å ha en lat belastning Delsett, definerer vi en klasse som strekker seg Abstrakt sett, og vi overstyrer noen av funksjonene.
Ved å løkke over alle biter som er 1 i mottakeren maske (eller posisjon) av Delsett, kan vi implementere Iterator og andre metoder i Abstrakt sett.
For eksempel størrelse() er antall 1s i mottakeren maske:
@ Override public int size () {return Integer.bitCount (mask); }Og inneholder () funksjonen er bare om den respektive biten i maske er 1 eller ikke:
@Override public boolean inneholder (@Nullable Object o) {Integer index = map.get (o); returindeks! = null && (maske & (1 << indeks))! = 0; }Vi bruker en annen variabel - gjenværende SetBits - for å endre det når vi henter det respektive elementet i delsettet vi endrer den biten til 0. Og så hasNext () sjekker om gjenværende SetBits er ikke null (det vil si at den har minst en bit med verdien på 1):
@Override public boolean hasNext () {return gjenværendeSetBits! = 0; }Og neste () funksjonen bruker det høyeste 1 i gjenværende SetBits, konverterer den deretter til 0, og returnerer også det respektive elementet:
@Override public E next () {int index = Integer.numberOfTrailingZeros (gjenværendeSetBits); if (index == 32) {kast nytt NoSuchElementException (); } gjenværende SetBits & = ~ (1 << indeks); return reverseMap.get (indeks); }6.3. PowerSet
Å ha en lat belastning PowerSet klasse, trenger vi en klasse som strekker seg Abstrakt sett
De størrelse() funksjonen er ganske enkelt 2 i kraft av settets størrelse:
@ Override public int size () {return (1 << this.set.size ()); }Ettersom strømsettet vil inneholde alle mulige delmengder av inngangssettet, så inneholder (Objekt o) funksjonen sjekker om alle elementene i objekt o finnes i reversMap (eller i inngangssettet):
@Override public boolean inneholder (@Nullable Object obj) {if (obj instanceof Set) {Set set = (Set) obj; return reverseMap.containsAll (sett); } returner falsk; }Å sjekke likhet mellom en gitt Gjenstand med denne klassen kan vi bare sjekke om inngangen sett er lik den gitte Gjenstand:
@Override offentlig boolsk er lik (@Nullable Object obj) {if (obj instanceof PowerSet) {PowerSet that = (PowerSet) obj; retur sett. likheter (that.set); } returner super.equals (obj); }De iterator () funksjon returnerer en forekomst av ListIterator som vi allerede definerte:
@Override offentlig Iterator iterator () {returner ny ListIterator(this.size ()) {@Override public Set next () {return new Subset (map, reverseMap, position ++); }}; } Guava-biblioteket bruker denne ideen om lat lat og disse PowerSet og Delsett er tilsvarende implementeringer av Guava-biblioteket.
For mer informasjon, sjekk kildekoden og dokumentasjonen.
Videre, hvis vi ønsker å gjøre parallell drift over delmengder i PowerSet, kan vi ringe Delsett for forskjellige verdier i a ThreadPool.
7. Oppsummering
For å oppsummere, studerte vi først hva som er et kraftuttak. Deretter genererte vi den ved hjelp av Guava-biblioteket. Etter det studerte vi tilnærmingen og hvordan vi skulle implementere den, og hvordan vi skrev en enhetstest for den.
Til slutt brukte vi Iterator grensesnitt for å optimalisere plassen for generering av delmengder og også deres interne elementer.
Som alltid er kildekoden tilgjengelig på GitHub.
