streamalism.org

1. סקירה כללית

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

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

2. יצירת תמורות

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

כידוע ממתמטיקה, לרצף של נ אלמנטים, יש n! תמורות שונות. n! ידוע כפעולה עובדתית:

n! = 1 * 2 * ... * n

כך, למשל, לרצף [1, 2, 3] יש שש תמורות:

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

המפתח גדל מהר מאוד - לרצף של 10 אלמנטים, יש לנו 3,628,800 תמורות שונות! במקרה הזה, אנו מדברים על רצפים מתמירים, בהם כל אלמנט שונה.

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

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

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

בואו נמחיש בדוגמה.

אנו רוצים ליצור את כל התמורות עבור רצף של ארבעה אלמנטים - [1, 2, 3, 4]. אז יהיו 24 תמורות. האיור שלהלן מציג את השלבים החלקיים של האלגוריתם:

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

אז, אנחנו מתחילים במדינה [1, 2, 3, 4] עם אינדקס השווה לאפס. אנו מחליפים את האלמנט הראשון עם כל אלמנט - כולל הראשון, שלא מחליף דבר - ועוברים למצב הבא.

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

2.2. יישום ג'אווה

האלגוריתם הכתוב בג'אווה הוא קצר:

חלופות ריקות סטטיות פרטיות פנימי (רצף רשימה, רשימה תוצאות, אינדקס int) {if (index == sequence.size () - 1) {permutations.add (ArrayList חדש (רצף)); } עבור (int i = index; i <sequence.size (); i ++) {swap (רצף, i, index); permutationsInternal (רצף, תמורות, אינדקס + 1); החלפה (רצף, i, אינדקס); }}

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

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

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

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

זה יכול להיות גם רעיון טוב להסתיר את השיחה הרקורסיבית הראשונה בשיטת חזית:

רשימה סטטית ציבורית createPermutations (רשימה ברשימה) {List תמורות = ArrayList חדש (); permutationsInternal (רצף, permutations, 0); תמורות חזרה; } 

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

3. יצירת ערכת הכוח של סט

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

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

כך, למשל, ניתן סט [א ב ג], ערכת הכוח מכילה שמונה קבוצות משנה:

[] [a] [b] [c] [a, b] [a, c] [b, c] [a, b, c]

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

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

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

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

3.2. יישום ג'אווה

האלגוריתם שלנו כתוב ב- Java די קריא:

כוח סטטי פרטי ריק סטנדרטי (ערכת רשימה, רשימה מערכת כוח, צבר רשימה, אינדקס int) {if (index == set.size ()) {results.add (ArrayList חדש (מצבר)); } אחר {accumulator.add (set.get (index)); powerSetInternal (סט, סט כוח, צבר, אינדקס + 1); accumulator.remove (accumulator.size () - 1); powerSetInternal (סט, סט כוח, צבר, אינדקס + 1); }}

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

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

בנוסף, אלמנט אחד מיוצג באות אחת (אופי בכיתה בג'אווה).

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

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

שוב, אנו מסתירים את היישום בשיטת חזית:

רשימה סטטית ציבורית createPowerset (רצף רשימה) {List כוח-כוח = ArrayList חדש (); powerSetInternal (רצף, כוח, חדש ArrayList (), 0); חזרת כוח; }

4. יצירת שילובים

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

k-שילוב סט ס היא תת קבוצה של k אלמנטים מובחנים מ S, איפה שלא חשוב סדר של פריטים

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

כך, למשל, לסט [א ב ג] יש לנו שלוש 2שילובים:

[a, b] [a, c] [b, c]

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

התשובה היא , אשר מעריך עד 120.

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

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

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

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

שווה ל -4,950, בעוד

יש 30 ספרות!

4.2. יישום ג'אווה

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

בואו נסתכל על יישום Java של האלגוריתם:

שילובים חלליים סטטיים פרטיים פנימיים (רשימת קלט סט, int k, רשימה תוצאות, מצבר ArrayList, אינדקס int) {int needToAccumulate = k - accumulator.size (); int canAcculumate = inputSet.size () - אינדקס; אם (accumulator.size () == k) {results.add (ArrayList חדש (מצבר)); } אחר אם (needToAccumulate <= canAcculumate) {ombinInternal (inputSet, k, results, accumulator, index + 1); accumulator.add (inputSet.get (אינדקס)); שילובים פנימיים (inputSet, k, תוצאות, מצבר, אינדקס + 1); accumulator.remove (accumulator.size () - 1); }}

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

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

• צריך לצבור - מציין כמה אלמנטים נוספים עלינו להוסיף לצבר שלנו כדי לקבל שילוב נכון
• יכול לצבור - מציין כמה אלמנטים נוספים שנוכל להוסיף לצבר שלנו

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

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

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

שוב, שיטת חזית מסתירה את היישום:

רשימה סטטית ציבורית שילובים (List inputSet, int k) {List תוצאות = ArrayList חדש (); ombinInternal (inputSet, k, תוצאות, ArrayList חדש (), 0); להחזיר תוצאות; }

5. סיכום

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

כרגיל, קוד המקור השלם, עם בדיקות, זמין ב- GitHub.