streamalism.org

1. הקדמה

במדריך זה, נדון בפתרון הבעיה של שילובי k ב- Java.

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

2. סקירת שילובים

פשוט שים, שילוב הוא תת קבוצה של אלמנטים מתוך קבוצה נתונה.

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

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

ישנן בעיות המחייבות אותנו להעריך את כל השילובים האפשריים. על מנת לעשות זאת, אנו מונים את השילובים השונים.

מספר הדרכים המובהקות לבחירת רכיבי "r" מתוך קבוצת האלמנטים "n" יכול לבוא לידי ביטוי מתמטית בנוסחה הבאה:

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

במקרים כאלה אנו עשויים לבחור באקראי כמה בחירות מייצגות. התהליך נקרא דְגִימָה.

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

3. אלגוריתמים רקורסיביים ליצירת שילובים

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

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

3.1. חלוקה לפי אלמנטים בערכה כולה

בוא נחלק את משימת הבחירה "r ” אלמנטים מ- “n ” פריטים על ידי בדיקת הפריטים אחד אחד. עבור כל פריט בערכה, אנו יכולים לכלול אותו בבחירה או לא לכלול אותו.

אם אנו כוללים את הפריט הראשון, עלינו לבחור "r – 1″ אלמנטים מהנותרים "n - 1 ″ פריטים. מצד שני, אם נזרוק את הפריט הראשון, עלינו לבחור "r ” אלמנטים מתוך שאר "n - 1 ″ פריטים.

זה יכול לבוא לידי ביטוי מתמטי כ:

עכשיו, בואו נבדוק את היישום הרקורסיבי של גישה זו:

עוזר חלל פרטי (שילובי רשימות, נתוני int [], int start, int end, int index) {if (index == data.length) {int [] שילוב = data.clone (); combinations.add (שילוב); } אחר אם (התחל <= סוף) {data [index] = התחלה; עוזר (שילובים, נתונים, התחלה + 1, סוף, אינדקס + 1); עוזר (שילובים, נתונים, התחלה + 1, סוף, אינדקס); }}

ה עוֹזֵר השיטה עושה לעצמה שתי שיחות רקורסיביות. השיחה הראשונה כוללת את האלמנט הנוכחי. השיחה השנייה זורקת את האלמנט הנוכחי.

לאחר מכן, בואו נכתוב את מחולל השילובים באמצעות זה עוֹזֵר שיטה:

רשימת ציבורים ליצור (int n, int r) {צירופי רשימה = ArrayList חדש (); עוזר (שילובים, int int [r], 0, n-1, 0); שילובי החזרה; }

בקוד לעיל, לִיצוֹר השיטה מגדירה את השיחה הראשונה אל עוֹזֵר שיטה ומעביר את הפרמטרים המתאימים.

לאחר מכן, בואו נקרא לשיטה זו כדי ליצור שילובים:

צירופי רשימות = צור (N, R); עבור (int [] שילוב: שילובים) {System.out.println (Arrays.toString (שילוב)); } System.out.printf ("יצר% d שילובים של% d פריטים מ-% d", combined.size (), R, N);

בעת ביצוע התוכנית, אנו מקבלים את הפלט הבא:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] יצר 10 שילובים של 2 פריטים מ -5

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

@Test הציבור בטל givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount () {SetRecursiveCombinationGenerator גנרטור = SetRecursiveCombinationGenerator חדש (); בחירת רשימה = מחולל. Generate (N, R); assertEquals (nCr, selection.size ()); }

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

לכן גישה זו לא עובדת אם מערך הקלט גדול.

3.2. חלוקה לפי אלמנטים בשילוב

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

ראשית, בואו להזמין את הפריטים בערכת הקלט באמצעות המדדים "1" עד "n ”. כעת נוכל לבחור את הפריט הראשון מתוך "n-r + 1 ″ פריטים.

נניח שבחרנו ב- kth פריט. ואז עלינו לבחור "r - 1 ″ פריטים מהנותרים “n - k ” פריטים באינדקס "k + 1 ″ ל "n ”.

אנו מבטאים את התהליך הזה בצורה מתמטית כ:

הַבָּא, בואו נכתוב את השיטה הרקורסיבית ליישום גישה זו:

עוזר חלל פרטי (שילובי רשימות, נתוני int [], int התחלה, int int, int index) {if (index == data.length) {int [] שילוב = data.clone (); combinations.add (שילוב); } אחר {int max = Math.min (end, end + 1 - data.length + index); עבור (int i = התחל; i <= max; i ++) {data [index] = i; עוזר (שילובים, נתונים, i + 1, סוף, אינדקס + 1); }}}

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

לאחר מכן, בואו נשתמש ב- עוֹזֵר שיטה ליצירת בחירות:

רשימת ציבורים ליצור (int n, int r) {צירופי רשימה = ArrayList חדש (); עוזר (שילובים, int [r] חדש, 0, n - 1, 0); שילובי החזרה; }

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

@Test הציבור בטל givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount () {SelectionRecursiveCombinationGenerator גנרטור = SelectionRecursiveCombinationGenerator חדש (); בחירת רשימה = מחולל. Generate (N, R); assertEquals (nCr, selection.size ()); }

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

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

4. אלגוריתם איטרטיבי

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

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

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

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

רשימת ציבורים ליצור (int n, int r) {צירופי רשימה = ArrayList חדש (); int [] שילוב = int int [r]; // אתחל עם השילוב הלקסיקוגרפי הנמוך ביותר עבור (int i = 0; i <r; i ++) {שילוב [i] = i; } בעוד (שילוב [r - 1] <n) {ombin.add (combined.clone ()); // ליצור צירוף הבא בסדר לקסיקוגרפי int t = r - 1; ואילו (t! = 0 && שילוב [t] == ​​n - r + t) {t--; } שילוב [t] ++; עבור (int i = t + 1; i <r; i ++) {שילוב [i] = שילוב [i - 1] + 1; }} שילובי החזרה; }

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

@Test הציבור בטל givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount () {מחולל IterativeCombinationGenerator = חדש IterativeCombinationGenerator (); בחירת רשימה = מחולל. Generate (N, R); assertEquals (nCr, selection.size ()); }

כעת, נשתמש בכמה ספריות Java כדי לפתור את הבעיה.

5. ספריות Java המיישמות שילובים

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

• אפאצ'י קומונס
• גויאבה
• CombinatoricsLib

5.1. אפאצ'י קומונס

ה CombinatoricsUtils class מ- Apache Commons מספק פונקציות שירות משולבות רבות. בפרט, ה שילובים אינטראטור שיטה מחזירה איטרטור שייצור שילובים בסדר לקסיקוגרפי.

ראשית, בואו נוסיף את התלות של Maven commons-math3 לפרויקט:

 org.apache.commons commons-math3 3.6.1 

הַבָּא, בואו נשתמש ב- שילובים אינטראטור שיטה להדפסת השילובים:

חלל סטטי ציבורי יוצר (int n, int r) {Iterator iterator = CombinatoricsUtils.combinationsIterator (n, r); ואילו (iterator.hasNext ()) {final int [] שילוב = iterator.next (); System.out.println (Arrays.toString (שילוב)); }}

5.2. גויאבה של גוגל

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

ראשית, בואו נוסיף את התלות של maven לספריית גויאבה לפרויקט:

 com.google.guava גויאבה 27.0.1-jre 

הַבָּא, בואו נשתמש ב- שילובים שיטה ליצירת שילובים:

מַעֲרֶכֶת שילובים = Sets.combinations (ImmutableSet.of (0, 1, 2, 3, 4, 5), 3);

הנה, אנו משתמשים ב- ImmutableSet.of שיטה ליצור סט מהמספרים הנתונים.

5.3. CombinatoricsLib

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

כדי להשתמש בו בפרויקט, בואו נוסיף את ה- combinatoricslib3 תלות במייבון:

 com.github.dpaukov combinatoricslib3 3.3.0 

הַבָּא, בואו נשתמש בספריה כדי להדפיס את השילובים:

Generator.combination (0, 1, 2, 3, 4, 5). פשוט (3) .stream (). ForEach (System.out :: println);

זה מייצר את הפלט הבא בביצוע:

[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 3, 4] [0, 3, 5] [0, 4, 5] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5]

דוגמאות נוספות זמינות בכתובת combinatoricslib3-example.

6. מסקנה

במאמר זה יישמנו כמה אלגוריתמים ליצירת שילובים.

סקרנו גם כמה יישומי ספרייה. בדרך כלל, נשתמש באלה במקום לגלגל משלנו.

כרגיל, ניתן למצוא את קוד המקור המלא ב- GitHub.