streamalism.org

1. הקדמה

במדריך זה נלמד את תהליך יצירת סט כוח של קבוצה נתונה בג'אווה.

כתזכורת מהירה, לכל סט גודל נ, יש סט כוח בגודל 2n. נלמד כיצד להשיג זאת בטכניקות שונות.

2. הגדרת סט כוח

ערכת הכוח של סט נתון ס הוא הסט של כל קבוצות המשנה של ס, כולל ס את עצמו ואת הסט הריק.

לדוגמא, עבור סט נתון:

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

ערכת הכוח היא:

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

מכיוון שמדובר גם בקבוצת משנה, סדר קבוצות המשנה הפנימיות שלה אינו חשוב והם יכולים להופיע בכל סדר:

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

3. ספריית גויאבה

לספריית גויאבה של גוגל יש כמה שימושיים מַעֲרֶכֶת כלי עזר, כגון ערכת החשמל. לפיכך, אנו יכולים להשתמש בו בקלות גם לקבל את סט הכוח של הסט הנתון:

@Test ציבורי בטל givenSet_WhenGuavaLibraryGeneratePowerSet_ThenItContainsAllSubsets () {ImmutableSet set = ImmutableSet.of ("APPLE", "ORANGE", "MANGO"); מַעֲרֶכֶת 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"))) ; }

גויאבה סט כוח פועלת באופן פנימי על פני איטרטור ממשק בדרך כאשר תת-קבוצה הבאה מתבקשת, תת-הקבוצה מחושבת ומוחזרת. לכן, מורכבות החלל מצטמצמת ל עַל) במקום O (2n).

אבל, איך גויאבה משיגה זאת?

4. גישה לייצור ערכות כוח

4.1. אַלגוֹרִיתְם

בואו נדון כעת בצעדים האפשריים ליצירת אלגוריתם לפעולה זו.

סט הכוח של סט ריק הוא {{}} בו הוא מכיל רק סט ריק אחד, אז זה המקרה הפשוט ביותר שלנו.

לכל סט ס מלבד הסט הריק, ראשית אנו מחלצים אלמנט אחד ושמו - אֵלֵמֶנט. ואז, לשאר האלמנטים של הסט subsetWithoutElementאנו מחשבים את סט הכוח שלהם באופן רקורסיבי - ושמנו אותו בערך כמו סט כוחסubsetWithoutElement. ואז, על ידי הוספת המופק אֵלֵמֶנט לכל המערכות סט כוחסubsetWithoutElement, אנחנו מקבלים סט כוחסubsetWithElement.

עכשיו, כוח הכוח ס הוא האיחוד של א powerSetSubsetWithoutElement ו powerSetSubsetWithElement:

בואו נראה דוגמה לערימת ערכת הכוח הרקורסיבית עבור הסט הנתון {“APPLE”, “ORANGE”, “MANGO”}.

כדי לשפר את הקריאות של התמונה אנו משתמשים בצורות קצרות של שמות: פ פירושו פונקציית סט כוח "A", "O", "M" הם צורות קצרות של "APPLE", "ORANGE", ו "מנגו", בהתאמה:

4.2. יישום

אז ראשית, בואו נכתוב את קוד Java לחילוץ אלמנט אחד ונקבל את קבוצות המשנה שנותרו:

אלמנט T = set.iterator (). הבא (); הגדר subsetWithoutElement = חדש HashSet (); עבור (T s: set) {if (! s.equals (element)) {subsetWithoutElement.add (s); }}

אז נרצה להשיג את כוח הכוח של subsetWithoutElement:

מַעֲרֶכֶת powersetSubSetWithoutElement = recursivePowerSet (subsetWithoutElement);

לאחר מכן, עלינו להוסיף את מערכת ההפעלה חזרה למקור:

מַעֲרֶכֶת powersetSubSetWithElement = HashSet חדש (); עבור (Set subsetWithoutElement: powerSetSubSetWithoutElement) {Set subsetWithElement = HashSet new (subsetWithoutElement); subsetWithElement.add (אלמנט); powerSetSubSetWithElement.add (subsetWithElement); }

סוף סוף האיחוד של powerSetSubSetWithoutElement ו powerSetSubSetWithElement הוא ערכת הכוח של ערכת הקלט הנתונה:

מַעֲרֶכֶת powerSet = HashSet חדש (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement);

אם נחבר את כל קטעי הקוד שלנו, נוכל לראות את המוצר הסופי שלנו:

סט ציבורי recursivePowerSet (Set set) {if (set.isEmpty ()) {Set ret = HashSet חדש (); ret.add (סט); להחזיר ret; } אלמנט T = set.iterator (). הבא (); Set subSetWithoutElement = getSubSetWithoutElement (set, element); מַעֲרֶכֶת powerSetSubSetWithoutElement = recursivePowerSet (subSetWithoutElement); מַעֲרֶכֶת powerSetSubSetWithElement = addElementToAll (powerSetSubSetWithoutElement, רכיב); מַעֲרֶכֶת powerSet = HashSet חדש (); powerSet.addAll (powerSetSubSetWithoutElement); powerSet.addAll (powerSetSubSetWithElement); החזר powerSet; } 

4.3. הערות לבדיקות יחידות

עכשיו בואו לבדוק. יש לנו כאן קצת קריטריונים לאישור:

• ראשית, אנו בודקים את גודל מערכת החשמל והיא חייבת להיות 2n עבור סט גודל נ.
• לאחר מכן, כל אלמנט יתרחש רק פעם אחת בקבוצת משנה ו 2n-1 קבוצות משנה שונות.
• לבסוף, כל קבוצת משנה חייבת להופיע פעם אחת.

אם כל התנאים הללו עברו, אנו יכולים להיות בטוחים שהפונקציה שלנו עובדת. עכשיו, מאז שהשתמשנו מַעֲרֶכֶת, אנחנו כבר יודעים שאין חזרה. במקרה כזה, עלינו לבדוק רק את גודל מערך הכוח ואת מספר המופעים של כל אלמנט בתת-קבוצות.

כדי לבדוק את גודל ערכת החשמל בה אנו יכולים להשתמש:

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

וכדי לבדוק את מספר המופעים של כל אלמנט:

מונה מפה = HashMap חדש (); עבור (Set subset: powerSet) {for (שם מחרוזת: subset) {int num = counter.getOrDefault (name, 0); counter.put (שם, מספר + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ()));

לבסוף, אם נוכל לחבר את כולם למבחן יחידה אחד:

@Test ציבורי בטל givenSet_WhenPowerSetIsCalculated_ThenItContainsAllSubsets () {Set set = RandomSetOfStringGenerator.generateRandomSet (); מַעֲרֶכֶת powerSet = PowerSet חדש (). recursivePowerSet (set); MatcherAssert.assertThat (powerSet, IsCollectionWithSize.hasSize ((1 << set.size ()))); מונה מפה = HashMap חדש (); עבור (Set subset: powerSet) {for (שם מחרוזת: subset) {int num = counter.getOrDefault (name, 0); counter.put (שם, מספר + 1); }} counter.forEach ((k, v) -> Assertions.assertEquals ((1 << (set.size () - 1)), v.intValue ())); }

5. אופטימיזציה

בחלק זה ננסה למזער את השטח ולצמצם את מספר הפעולות הפנימיות לחישוב ההספק שנקבע בצורה אופטימלית.

5.1. מבנה נתונים

כפי שאנו רואים בגישה הנתונה, אנו זקוקים להרבה חיסורים בשיחה הרקורסיבית, אשר גוזלת זמן וזיכרון רב.

במקום זאת, אנו יכולים למפות כל קבוצה או קבוצת משנה לתפיסות אחרות כדי להפחית את מספר הפעולות.

ראשית, עלינו להקצות מספר הולך וגדל החל מ- 0 לכל אובייקט בסט הנתון ס מה שאומר שאנחנו עובדים עם רשימת מספרים מסודרת.

למשל לסט הנתון {“APPLE”, “ORANGE”, “MANGO”} אנחנו מקבלים:

"APPLE" -> 0

"כתום" ->

"MANGO" -> 2

אז, מעכשיו, במקום ליצור קבוצות משנה של ס, אנו מייצרים אותם לרשימה המסודרת של [0, 1, 2], וכפי שהיא מסודרת נוכל לדמות חיסורים על ידי אינדקס התחלתי.

לדוגמא, אם אינדקס ההתחלה הוא 1 זה אומר שאנחנו מייצרים את ערכת הכוח של [1,2].

כדי לאחזר מזהה ממופה מהאובייקט ולהיפך, אנו מאחסנים את שני צידי המיפוי. בעזרת הדוגמה שלנו, אנו מאחסנים את שניהם (“MANGO” -> 2) ו (2 -> "MANGO"). כאשר מיפוי המספרים החל מאפס, כך עבור המפה ההפוכה שם אנו יכולים להשתמש במערך פשוט כדי לאחזר את האובייקט המתאים.

אחת היישומים האפשריים של פונקציה זו תהיה:

מפת מפה פרטית = HashMap חדש (); רשימה פרטית reverseMap = ArrayList חדש (); חלל פרטי initializeMap (אוסף האוסף) {int mapId = 0; עבור (T c: collection) {map.put (c, mapId ++); reverseMap.add (c); }}

כעת, כדי לייצג קבוצות משנה יש שני רעיונות ידועים:

1. ייצוג אינדקס
2. ייצוג בינארי

5.2. ייצוג אינדקס

כל קבוצת משנה מיוצגת על ידי אינדקס הערכים שלה. לדוגמא, מיפוי האינדקס של הסט הנתון {“APPLE”, “ORANGE”, “MANGO”} יהיה:

{{} -> {} [0] -> {"APPLE"} [1] -> {"ORANGE"} [0,1] -> {"APPLE", "ORANGE"} [2] -> {" MANGO "} [0,2] -> {" APPLE "," MANGO "} [1,2] -> {" ORANGE "," MANGO "} [0,1,2] -> {" APPLE "," כתום "," MANGO "}}

לכן, אנו יכולים לאחזר את הסט המתאים מתוך קבוצת מדדים עם המיפוי הנתון:

סט פרטי unMapIndex (סט סטים) {סט ret = HashSet חדש (); עבור (Set s: sets) {ערכת משנה HashSet = HashSet חדשה (); עבור (שלם i: s) {subset.add (reverseMap.get (i)); } ret.add (תת קבוצה); } להחזיר ret; }

5.3. ייצוג בינארי

לחלופין, אנו יכולים לייצג כל קבוצת משנה באמצעות בינארי. אם קיים אלמנט מהקבוצה בפועל בקבוצת משנה זו הערך שלה הוא 1; אחרת זה כן 0.

לדוגמא הפירות שלנו, ערכת הכוח תהיה:

{[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"}}

אז נוכל לאחזר את הסט המתאים מתת-בינארית עם המיפוי הנתון:

סט פרטי unMapBinary (אוסף סטים) {סט ret = HashSet חדש (); עבור (List s: sets) {קבוצת משנה של HashSet = HashSet חדש (); עבור (int i = 0; i <s.size (); i ++) {if (s.get (i)) {subset.add (reverseMap.get (i)); }} ret.add (תת קבוצה); } להחזיר ret; }

5.4. יישום אלגוריתם רקורסיבי

בשלב זה ננסה ליישם את הקוד הקודם באמצעות שני מבני הנתונים.

לפני שאנחנו קוראים לאחת מהפונקציות הללו, עלינו להתקשר ל- initializeMap שיטה להשיג את הרשימה שהוזמנה. כמו כן, לאחר יצירת מבנה הנתונים שלנו, עלינו להתקשר למערכת המתאימה בטל את המפה פונקציה כדי לאחזר את האובייקטים בפועל:

סט ציבורי recursivePowerSetIndexRepresentation (ערכת אוסף) {initializeMap (set); מַעֲרֶכֶת powerSetIndices = recursivePowerSetIndexRepresentation (0, set.size ()); להחזיר unMapIndex (powerSetIndices); }

אז בואו ננסה את היד שלנו בייצוג המדד:

סט פרטי recursivePowerSetIndexRepresentation (int idx, int n) {if (idx == n) {Set ריק = HashSet חדש (); empty.add (HashSet חדש ()); חזור ריק; } הגדר powerSetSubset = recursivePowerSetIndexRepresentation (idx + 1, n); מַעֲרֶכֶת powerSet = HashSet חדש (powerSetSubset); עבור (Set s: powerSetSubset) {HashSet subSetIdxInclusive = HashSet חדש (ים); subSetIdxInclusive.add (idx); powerSet.add (subSetIdxInclusive); } להחזיר את powerSet; }

עכשיו, בואו נראה את הגישה הבינארית:

סט פרטי recursivePowerSetBinaryRepresentation (int idx, int n) {if (idx == n) {Set powerSetOfEmptySet = HashSet חדש (); powerSetOfEmptySet.add (Arrays.asList (בוליאני חדש [n])); החזר powerSetOfEmptySet; } הגדר powerSetSubset = recursivePowerSetBinaryRepresentation (idx + 1, n); מַעֲרֶכֶת powerSet = HashSet חדש (); עבור (רשימה s: powerSetSubset) {רשימה subSetIdxExclusive = ArrayList (ים) חדשים; subSetIdxExclusive.set (idx, false); powerSet.add (subSetIdxExclusive); רשימה subSetIdxInclusive = ArrayList (ים) חדשים; subSetIdxInclusive.set (idx, true); powerSet.add (subSetIdxInclusive); } להחזיר את powerSet; }

5.5. חזר דרך [0, 2n)

עכשיו, יש אופטימיזציה נחמדה שאנחנו יכולים לעשות עם הייצוג הבינארי. אם נסתכל על זה, נוכל לראות שכל שורה מקבילה לפורמט הבינארי של מספר ב- [0, 2n).

אז אם נחזור באמצעות מספרים מ- 0 ל 2n, אנו יכולים להמיר אינדקס זה לבינארי, ולהשתמש בו ליצירת ייצוג בוליאני של כל קבוצת משנה:

רשימה פרטית iterativePowerSetByLoopOverNumbers (int n) {רשימה powerSet = ArrayList חדש (); עבור (int i = 0; i <(1 << n); i ++) {תת-קבוצה רשימה = ArrayList חדש (n); עבור (int j = 0; j <n; j ++) תת קבוצה.תוספת (((1 <0); powerSet.add (תת קבוצה);} להחזיר powerSet;}

5.6. קבוצות משנה מינימליות לשינוי לפי קוד אפור

כעת, אם נגדיר פונקציה כלשהי כלשהי מייצוג בינארי של אורך נ למספר ב [0, 2n)אנו יכולים ליצור תת קבוצות בכל סדר שנרצה.

קוד אפור הוא פונקציה ידועה המשמשת להפקת ייצוגים בינאריים של מספרים כך שהייצוג הבינארי של מספרים עוקבים שונה בסיבית אחת בלבד (אפילו ההבדל בין המספר האחרון והראשון הוא אחד).

כך אנו יכולים לבצע אופטימיזציה זו עוד מעט:

רשימה פרטית iterativePowerSetByLoopOverNumbersWithGrayCodeOrder (int n) {List powerSet = ArrayList חדש (); עבור (int i = 0; i <(1 << n); i ++) {תת קבוצה רשימה = ArrayList חדש (n); עבור (int j = 0; j > 1); subset.add ((((1 <0);} powerSet.add (subset);} return powerSet;}

6. טעינה עצלה

כדי למזער את השימוש בחלל של ערכת החשמל, כלומר O (2n), אנו יכולים להשתמש ב- איטרטור ממשק להביא כל קבוצת משנה, וגם כל רכיב בכל קבוצת משנה בעצלתיים.

6.1. ListIterator

ראשית, להיות מסוגל לחזור מ 0 ל 2nאנחנו צריכים לקבל מבצע מיוחד איטרטור שעוברת על טווח זה אך לא צורכת את כל הטווח מראש.

כדי לפתור בעיה זו, נשתמש בשני משתנים; אחד לגודל, כלומר 2n, ואחד נוסף עבור אינדקס המשנה הנוכחי. שֶׁלָנוּ hasNext () פונקציה תבדוק זאת עמדה זה פחות מ גודל:

מחלקה מופשטת ListIterator מיישמת Iterator {position מוגן int = 0; גודל פרטי פרטי; ListIterator ציבורי (גודל int) {this.size = size; } @Override בוליאני ציבורי hasNext () {עמדה חזרה <גודל; }}

ושלנו הַבָּא() פונקציה מחזירה את קבוצת המשנה עבור הזרם עמדה ומגדיל את הערך של עמדה על ידי אחד:

@Override public הגדר הבא () {להחזיר תת-קבוצה חדשה (מפה, reverseMap, position ++); }

6.2. קבוצת משנה

שיהיה עומס עצלן קבוצת משנה, אנו מגדירים מעמד שמתארך תקציר סטואנחנו עוקפים חלק מתפקידיו.

על ידי לולאה על כל החלקים שיש 1 בקבלה מסכה (או מיקום) של ה תת קבוצה, אנו יכולים ליישם את איטרטור ושיטות אחרות ב תקציר סט.

לדוגמא, ה גודל() הוא המספר של 1s בקבלה מסכה:

@ גודל גודל ציבורי אינטראקטיבי () {להחזיר Integer.bitCount (מסכה); }

וה מכיל () הפונקציה היא רק אם הסיביות המתאימה ב- מסכה הוא 1 או שלא:

@ Override בוליאני ציבורי מכיל (@ אובייקט מוחלט o) {אינדקס שלם = map.get (o); אינדקס החזרה! = null && (מסכה & (1 << אינדקס))! = 0; }

אנו משתמשים במשתנה אחר - restSetBits - כדי לשנות אותו בכל פעם שאנו מאחזרים את האלמנט המתאים שלו בתת-המשנה אנו משנים את הסיבית הזו ל 0. אז ה hasNext () בודק אם restSetBits אינו אפס (כלומר יש בו לפחות ביט אחד עם הערך 1):

@Override בוליאני ציבורי hasNext () {להחזיר leftSetBits! = 0; }

וה הַבָּא() הפונקציה משתמשת נכון ביותר 1 בתוך ה restSetBitsואז ממיר אותו ל- 0, ומחזיר גם את האלמנט המתאים:

@ עקוב על הציבור E הבא () {int index = Integer.numberOfTrailingZeros (leftSetBits); אם (אינדקס == 32) {זרוק NoSuchElementException חדש (); } restSetBits & = ~ (1 << אינדקס); להחזיר reverseMap.get (אינדקס); }

6.3. סט כוח

שיהיה עומס עצלן סט כוח בכיתה, אנחנו צריכים שיעור שמתארך תקציר סט.

ה גודל() הפונקציה היא פשוט 2 בעוצמה של גודל הסט:

@ גודל גודל ציבורי אינטראקטיבי () {להחזיר (1 << this.set.size ()); }

מכיוון שמערכת החשמל תכיל את כל קבוצות המשנה האפשריות של מערך הקלט, כך מכיל (אובייקט o) פונקציה בודקת אם כל האלמנטים של אובייקט o קיימים ב הפוך מפה (או בערכת הקלט):

@ Override בוליאני ציבורי מכיל (@ אובייקט אובייקטיבי מוחלט) {if (obj instanceof Set) {Set set = (Set) obj; להחזיר reverseMap.containsAll (set); } להחזיר שקר; }

כדי לבדוק שוויון של נתון לְהִתְנַגֵד עם מחלקה זו, אנו יכולים לבדוק רק אם הקלט מַעֲרֶכֶת שווה לנתון לְהִתְנַגֵד:

@ ביטול בוליאני ציבורי שווה ל- (אובייקט אובייקטיבי מוחלט) {if (obj instanceof PowerSet) {PowerSet that = (PowerSet) obj; להחזיר set.equals (that.set); } להחזיר super.equals (obj); }

ה איטרטור () פונקציה מחזירה מופע של ListIterator שהגדרנו כבר:

@ איטרטור ציבורי @ Override iterator () {להחזיר ListIterator חדש(this.size ()) {@Override public הגדר הבא () {החזר תת קבוצה חדשה (מפה, reverseMap, position ++); }}; }

ספריית גויאבה משתמשת ברעיון זה של עצלות עצלן ואלו סט כוח ו תת קבוצה הם היישומים המקבילים של ספריית גויאבה.

לקבלת מידע נוסף, בדוק את קוד המקור ותיעודם.

יתר על כן, אם אנו רוצים לבצע פעולה מקבילה על קבוצות משנה ב סט כוחאנחנו יכולים להתקשר תת קבוצה לערכים שונים ב- ThreadPool.

7. סיכום

לסיכום, ראשית, למדנו מהי סט כוח. לאחר מכן, יצרנו אותו באמצעות ספריית גויאבה. לאחר מכן, למדנו את הגישה וכיצד עלינו ליישם אותה, וכן כיצד לכתוב עבורה מבחן יחידה.

לבסוף, השתמשנו ב- איטרטור ממשק כדי לייעל את שטח ייצור קבוצות המשנה וגם את האלמנטים הפנימיים שלהם.

כמו תמיד קוד המקור זמין ב- GitHub.