Opnåelse af et elsæt af et sæt i Java
1. Introduktion
I denne vejledning studerer vi processen med at generere et elsæt af et givet sæt i Java.
Som en hurtig påmindelse for hvert sæt af størrelser n, der er et strømsæt af størrelse 2n. Vi lærer at få det ved hjælp af forskellige teknikker.
2. Definition af et elsæt
Strømsættet for et givet sæt S er sættet med alle delmængder af S, inklusive S sig selv og det tomme sæt.
For eksempel for et givet sæt:
{"APPLE", "ORANGE", "MANGO"}strømforsyningen er:
{{}, {"APPLE"}, {"ORANGE"}, {"APPLE", "ORANGE"}, {"MANGO"}, {"APPLE", "MANGO"}, {"ORANGE", "MANGO" }, {"APPLE", "ORANGE", "MANGO"}}Da det også er et sæt delsæt, er rækkefølgen af dets interne delsæt ikke vigtigt, og de kan vises i enhver rækkefølge:
{{}, {"MANGO"}, {"ORANGE"}, {"ORANGE", "MANGO"}, {"APPLE"}, {"APPLE", "MANGO"}, {"APPLE", "ORANGE" }, {"APPLE", "ORANGE", "MANGO"}}3. Guava Bibliotek
Google Guava-biblioteket har nogle nyttige Sæt hjælpeprogrammer, såsom strømforsyningen. Således kan vi også nemt bruge det til at få strømforsyningen til det givne sæt:
@Test offentlig ugyldighed givenSet_WhenGuavaLibraryGeneratePowerSet_ThenItContainsAllSubsets () {ImmutableSet set = ImmutableSet.of ("APPLE", "ORANGE", "MANGO"); Sæt powerSet = Sets.powerSet (sæt); 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 interface på den måde, når den næste delmængde anmodes, beregnes og returneres delmængden. Så pladsens kompleksitet er reduceret til På) i stedet for O (2n).
Men hvordan opnår Guava dette?
4. Power Set Generation Approach
4.1. Algoritme
Lad os nu diskutere de mulige trin til oprettelse af en algoritme til denne operation.
Strømforsyningen til et tomt sæt er {{}} hvor den kun indeholder et tomt sæt, så det er vores enkleste sag.
For hvert sæt S bortset fra det tomme sæt udtrækker vi først et element og navngiver det - element. Derefter for resten af elementerne i et sæt subsetWithoutElement, vi beregner deres effektsæt rekursivt - og navngiver det noget lignende powerSetSubsetWithoutElement. Derefter ved at tilføje det ekstraherede element til alle sætter ind powerSetSubsetWithoutElement, vi får powerSetSubsetWithElement.
Nu er strømmen sat S er foreningen af en powerSetSubsetWithoutElement og en powerSetSubsetWithElement:
Lad os se et eksempel på den rekursive power set stack for det givne sæt {“APPLE”, “ORANGE”, “MANGO”}.
For at forbedre læsbarheden af billedet bruger vi korte navneformer: P betyder power set-funktion og “A”, “O”, “M” er korte former for "APPLE", "ORANGE", og “MANGO”, henholdsvis:
4.2. Implementering
Så lad os først skrive Java-koden til udpakning af et element og få de resterende delmængder:
T-element = sæt.iterator (). Næste (); Indstil subsetWithoutElement = nyt HashSet (); for (T s: sæt) {if (! s.equals (element)) {subsetWithoutElement.add (s); }}Derefter vil vi få powerset af subsetWithoutElement:
Sæt powersetSubSetWithoutElement = recursivePowerSet (subsetWithoutElement); Dernæst er vi nødt til at tilføje dette powerset tilbage til originalen:
Sæt powersetSubSetWithElement = ny HashSet (); for (Set subsetWithoutElement: powerSetSubSetWithoutElement) {Set subsetWithElement = new HashSet (subsetWithoutElement); subsetWithElement.add (element); powerSetSubSetWithElement.add (subsetWithElement); } Endelig foreningen af powerSetSubSetWithoutElement og powerSetSubSetWithElement er effektsættet for det givne indgangssæt:
Sæt powerSet = nyt HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); Hvis vi lægger alle vores kodestykker sammen, kan vi se vores endelige produkt:
offentligt sæt recursivePowerSet (Set set) {if (set.isEmpty ()) {Set ret = nyt HashSet (); ret.add (sæt); returnere ret; } T element = set.iterator (). Næste (); Set subSetWithoutElement = getSubSetWithoutElement (sæt, element); Sæt powerSetSubSetWithoutElement = recursivePowerSet (subSetWithoutElement); Sæt powerSetSubSetWithElement = addElementToAll (powerSetSubSetWithoutElement, element); Sæt powerSet = nyt HashSet (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); returner powerSet; } 4.3. Bemærkninger til enhedstest
Lad os nu teste. Vi har nogle kriterier her for at bekræfte:
- Først kontrollerer vi størrelsen på strømforsyningen, og den skal være 2n for et sæt størrelse n.
- Derefter vil hvert element kun forekomme en gang i et undersæt og 2n-1 forskellige undergrupper.
- Endelig skal hvert undersæt vises en gang.
Hvis alle disse betingelser bestod, kan vi være sikre på, at vores funktion fungerer. Nu, da vi har brugt det Sæt, vi ved allerede, at der ikke er nogen gentagelse. I så fald behøver vi kun kontrollere størrelsen på strømforsyningen og antallet af forekomster af hvert element i delmængderne.
For at kontrollere størrelsen på strømforsyningen kan vi bruge:
MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ())));Og for at kontrollere antallet af forekomster af hvert element:
Korttæller = ny 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 ()));Endelig, hvis vi kan sætte alle sammen i en enhedstest:
@Test offentlig ugyldighed givenSet_WhenPowerSetIsCalculated_ThenItContainsAllSubsets () {Set set = RandomSetOfStringGenerator.generateRandomSet (); Sæt powerSet = nyt PowerSet (). recursivePowerSet (sæt); MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ()))); Korttæller = ny 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. Optimering
I dette afsnit forsøger vi at minimere pladsen og reducere antallet af interne operationer for at beregne den indstillede effekt på en optimal måde.
5.1. Datastruktur
Som vi kan se i den givne tilgang, har vi brug for en masse subtraktioner i det rekursive opkald, som bruger meget tid og hukommelse.
I stedet kan vi kortlægge hvert sæt eller delmængde til nogle andre begreber for at reducere antallet af operationer.
Først skal vi tildele et stigende antal startende fra 0 til hvert objekt i det givne sæt S hvilket betyder, at vi arbejder med en ordnet liste med numre.
For eksempel for det givne sæt {“APPLE”, “ORANGE”, “MANGO”} vi får:
“APPLE” -> 0
“ORANGE” ->
“MANGO” -> 2
Så fra nu af i stedet for at generere delmængder af S, genererer vi dem til den ordnede liste over [0, 1, 2], og som den er bestilt, kan vi simulere subtraktioner med et startindeks.
For eksempel, hvis startindekset er 1 betyder det, at vi genererer effektsættet på [1,2].
For at hente kortlagt id fra objektet og omvendt gemmer vi begge sider af kortlægning. Ved hjælp af vores eksempel gemmer vi begge (“MANGO” -> 2) og (2 -> “MANGO”). Da kortlægningen af numre startede fra nul, så for det omvendte kort der kan vi bruge et simpelt array til at hente det respektive objekt.
En af de mulige implementeringer af denne funktion ville være:
privat kortkort = nyt HashMap (); privat liste reverseMap = ny ArrayList (); privat tomrum initializeMap (samling samling) {int mapId = 0; for (Tc: samling) {map.put (c, mapId ++); reverseMap.add (c); }}For at repræsentere delmængder er der to velkendte ideer:
- Indeksrepræsentation
- Binær repræsentation
5.2. Indeksrepræsentation
Hver delmængde er repræsenteret ved indekset over dens værdier. For eksempel indeksmappningen af det givne sæt {“APPLE”, “ORANGE”, “MANGO”} ville være:
{{} -> {} [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 sæt fra en delmængde af indekser med den givne kortlægning:
privat sæt unMapIndex (sæt sæt) {Set ret = nyt HashSet (); for (Set s: sets) {HashSet subset = new HashSet (); for (Heltal i: s) {undersæt.add (reverseMap.get (i)); } ret.add (delmængde); } returnere ret; } 5.3. Binær repræsentation
Eller vi kan repræsentere hver delmængde ved hjælp af binær. Hvis der findes et element i det aktuelle sæt i denne delmængde, er dens respektive værdi 1; ellers er det 0.
For vores frugteksempel ville kraftindstillingen 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 respektive sæt fra en binær delmængde med den givne kortlægning:
privat sæt unMapBinary (samling sæt) {Set ret = nyt 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 (undergruppe); } returnere ret; }
5.4. Rekursiv algoritmeimplementering
I dette trin forsøger vi at implementere den tidligere kode ved hjælp af begge datastrukturer.
Før vi ringer til en af disse funktioner, skal vi ringe til initializeMap metode til at få den bestilte liste. Efter oprettelse af vores datastruktur skal vi også ringe til den respektive unMap funktion til at hente de faktiske objekter:
offentligt sæt recursivePowerSetIndexRepresentation (Collection set) {initializeMap (set); Sæt powerSetIndices = recursivePowerSetIndexRepresentation (0, set.size ()); returner unMapIndex (powerSetIndices); } Så lad os prøve vores hånd på indeksrepræsentationen:
privat sæt recursivePowerSetIndexRepresentation (int idx, int n) {if (idx == n) {Set tom = ny HashSet (); empty.add (nyt HashSet ()); returner tom; } Indstil powerSetSubset = rekursivPowerSetIndexRepresentation (idx + 1, n); Sæt powerSet = nyt HashSet (powerSetSubset); for (Set s: powerSetSubset) {HashSet subSetIdxInclusive = nye HashSet (s); subSetIdxInclusive.add (idx); powerSet.add (subSetIdxInclusive); } returner powerSet; } Lad os nu se den binære tilgang:
privat sæt recursivePowerSetBinaryRepresentation (int idx, int n) {if (idx == n) {Set powerSetOfEmptySet = ny HashSet (); powerSetOfEmptySet.add (Arrays.asList (ny boolsk [n])); returner powerSetOfEmptySet; } Indstil powerSetSubset = recursivePowerSetBinaryRepresentation (idx + 1, n); Sæt powerSet = nyt HashSet (); for (List s: powerSetSubset) {List subSetIdxExclusive = new ArrayList (s); subSetIdxExclusive.set (idx, false); powerSet.add (subSetIdxExclusive); Liste subSetIdxInclusive = nye ArrayList (er); subSetIdxInclusive.set (idx, sand); powerSet.add (subSetIdxInclusive); } returner powerSet; }
5.5. Iterere igennem [0, 2n)
Nu er der en god optimering, vi kan gøre med den binære repræsentation. Hvis vi ser på det, kan vi se, at hver række svarer til det binære format for et tal i [0, 2n).
Så hvis vi gentager tal fra 0 til 2n, vi kan konvertere dette indeks til binært og bruge det til at oprette en boolsk repræsentation af hver delmængde:
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 ++) delmængde.add (((1 <0); powerSet.add (delmængde);} returner powerSet;}
5.6. Delsæt med minimale ændringer efter grå kode
Nu, hvis vi definerer en hvilken som helst bijektiv funktion fra binær repræsentation af længde n til et nummer i [0, 2n), kan vi generere undersæt i den rækkefølge, vi ønsker.
Grå kode er en velkendt funktion, der bruges til at generere binære repræsentationer af tal, så den binære repræsentation af fortløbende tal kun adskiller sig med en bit (selv forskellen på det sidste og første tal er en).
Vi kan således optimere dette lidt længere:
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 at minimere pladsforbruget af strømforsyning, hvilket er O (2n), kan vi bruge Iterator interface til at hente hvert delsæt, og også hvert element i hvert delsæt doven.
6.1. ListIterator
For det første at være i stand til at gentage fra 0 til 2n, vi skulle have en speciel Iterator der løber over dette interval, men ikke forbruger hele området på forhånd.
For at løse dette problem bruger vi to variabler; en for størrelsen, som er 2n, og en anden for det aktuelle delsætindeks. Vores hasNext () funktion vil kontrollere det position er mindre end størrelse:
abstrakt klasse ListIterator implementerer Iterator {beskyttet int position = 0; privat int størrelse offentlig ListIterator (int størrelse) {this.size = størrelse; } @ Override offentlig boolsk hasNext () {returposition <størrelse; }}Og vores Næste() funktion returnerer delsættet for den aktuelle position og øger værdien af position af en:
@ Override public Set next () {return new Subset (map, reverseMap, position ++); }6.2. Delmængde
At have en doven belastning Delmængde, definerer vi en klasse, der strækker sig Abstrakt sæt, og vi tilsidesætter nogle af dens funktioner.
Ved at sløjfe over alle bits, der er 1 i modtagelsen maske (eller position) af Delmængde, kan vi implementere Iterator og andre metoder i Abstrakt sæt.
F.eks størrelse() er antallet af 1s i modtagelsen maske:
@ Override public int-størrelse () {return Integer.bitCount (mask); }Og indeholder() funktion er bare om den respektive bit i maske er 1 eller ikke:
@Override public boolean indeholder (@Nullable Object o) {Integer index = map.get (o); returindeks! = null && (maske & (1 << indeks))! = 0; }Vi bruger en anden variabel - resterende SetBits - for at ændre det, når vi henter dets respektive element i delmængden, ændrer vi den bit til 0. Derefter hasNext () kontrollerer, om resterende SetBits er ikke nul (dvs. den har mindst en bit med en værdi på 1):
@Override offentlig boolsk hasNext () {return leftSetBits! = 0; }Og Næste() funktion bruger det mest rigtige 1 i resterende SetBits, konverterer det derefter til 0, og returnerer også det respektive element:
@Override public E next () {int index = Integer.numberOfTrailingZeros (gjenværendeSetBits); hvis (indeks == 32) {kast nyt NoSuchElementException (); } resterende SetBits & = ~ (1 << indeks); returner reverseMap.get (indeks); }6.3. PowerSet
At have en doven belastning PowerSet klasse, vi har brug for en klasse, der strækker sig Abstrakt sæt
Det størrelse() funktion er simpelthen 2 til styrken af sætets størrelse:
@Override public int size () {return (1 << this.set.size ()); }Da strømsættet vil indeholde alle mulige delmængder af indgangssættet, så indeholder (Objekt o) funktion kontrollerer, om alle elementer i objekt o findes i reverseMap (eller i indgangssættet):
@Override public boolean indeholder (@Nullable Object obj) {if (obj instanceof Set) {Set set = (Set) obj; returnere reverseMap.containsAll (sæt); } returner falsk; }At kontrollere lighed mellem et givet Objekt med denne klasse kan vi kun kontrollere, om input sæt er lig med det givne Objekt:
@Override offentlige boolske er lig med (@Nullable Object obj) {if (obj instanceof PowerSet) {PowerSet that = (PowerSet) obj; returner sæt. ligninger (that.set); } returner super.equals (obj); }Det iterator () funktion returnerer en forekomst af ListIterator som vi allerede definerede:
@Override offentlig Iterator iterator () {returner ny ListIterator(this.size ()) {@Override public Set next () {return new Subset (map, reverseMap, position ++); }}; } Guava-biblioteket bruger denne idé med doven belastning og disse PowerSet og Delmængde er de tilsvarende implementeringer af Guava-biblioteket.
For mere information, se deres kildekode og dokumentation.
Desuden, hvis vi vil udføre parallel operation over delmængder i PowerSet, vi kan ringe Delmængde for forskellige værdier i a TrådPool.
7. Resume
For at opsummere undersøgte vi først, hvad der er et strømforsyning. Derefter genererede vi det ved hjælp af Guava Library. Derefter studerede vi fremgangsmåden, og hvordan vi skulle implementere den, og hvordan vi skrev en enhedstest til den.
Endelig brugte vi Iterator interface til at optimere pladsen til generering af undergrupper og også deres interne elementer.
Som altid er kildekoden tilgængelig på GitHub.
