בעיה ה'
הוראות המופיעות בגוף של מבנה while ומתבצעות כל עוד תנאי הלולאה מתקיים צריכות להיות מוזזות ימינה ביחס לשורה הראשונה במבנה. הקוד התקין:
age = input(‘Insert age; -1 to stop: ‘)
while age != ‘-1’:
print(age)
age = input(‘Insert age; -1 to stop: ‘)
נתונה books – רשימה של שמות ספרים. ברשימה שלושה שמות או יותר, ואין שם המופיע בה יותר מפעם אחת. לדוגמה זו רשימה שיש בה ארבעה שמות ספרים –
[‘1984’, ‘Dracula’, ‘Ulysses’, ‘Beloved’]
יש לכתוב קוד המדפיס את כל תת הרשימות של הרשימה books שהן בגודל 3 ומקיימות את שני התנאים האלה: אין תת רשימה שבה שם ספר מופיע יותר מפעם אחת, ואין תת רשימה שכל שמות הספרים המופיעים בה מופיעים גם בתת רשימה אחרת. שמות הספרים בכל תת רשימה יכולים להופיע בסדר כלשהו. לדוגמה, עבור רשימות הדוגמה books הקוד יוכל להדפיס את תת הרשימות האלה:
[‘1984’, ‘Dracula’, ‘Ulysses’]
[‘1984’, ‘Dracula’, ‘Beloved’]
[‘1984’, ‘Ulysses’, ‘Beloved’]
[‘Dracula’, ‘Ulysses’, ‘Beloved’]
אם הודפסו תת רשימות אלו, לא תודפס תת רשימה המכילה שלשת שמות נוספת, גם אם סדר השלשה הוא אחר. למשל לא יודפסו תת הרשימות האלה –
[‘Dracula’, ‘1984’, ‘Ulysses’]
[‘1984’, ‘Beloved’, ‘Dracula’]
לפתרון בקוד ראו כאן.
פתרון מפורט
הבעיה העקרונית העומדת בבסיס השאלה היא זו:
נתון אוסף של ערכים שמספר הערכים בו אינו קטן מ-n.
יש ליצור את כל תתי האוספים של האוסף הנתון שהם בגודל n,
אין בהם כפילויות (כלומר ערך המופיע יותר מפעם אחת),
והם שונים זה מזה מבחינת תכנם.
בניסוחה הקונקרטי כאן הבעיה היא למצוא, על יסוד הרשימה books (הכוללת לפי הבעיה לפחות שלושה שמות ספרים), את כל שלשות שמות הספרים השונות זו מזו מבחינת תכנן, ושבכל אחת מהן אין שם ספר המופיע יותר מפעם אחת. קודם שנפתור בעיה זו ננסה לפתור בעיה פשוטה יותר ממנה: נמצא את כל זוגות שמות הספרים השונים זה מזה שיש ברשימה books. הנה כל הזוגות האלה –
[‘1984’, ‘Dracula’]
[‘1984’, ‘Ulysses’]
[‘1984’, ‘Beloved’]
[‘Dracula’, ‘Ulysses’]
[‘Dracula’, ‘Beloved’]
[‘Ulysses’, ‘Beloved’]
והנה נסיון ראשון למצוא את הזוגות האלה, בשימוש בלולאה מקוננת –
books = [‘1984’, ‘Dracula’, ‘Ulysses’, ‘Beloved’]
for book1 in books:
for book2 in books:
print([book1, book2])
הלולאה החיצונית סורקת את כל שמות הספרים ברשימה books. עבור כל שם ספר, הלולאה הפנימית סורקת גם היא את כל שמות הספרים ברשימה, ועבור כל שם ספר מדפיסה זוג שיש בו את השם הזה (שני בזוג) ואת השם הנסרק בלולאה החיצונית (ראשון בזוג). הנה הפלט של קטע הקוד –
[‘1984’, ‘1984’]
[‘1984’, ‘Dracula’]
[‘1984’, ‘Ulysses’]
[‘1984’, ‘Beloved’]
[‘Dracula’, ‘1984’]
[‘Dracula’, ‘Dracula’]
[‘Dracula’, ‘Ulysses’]
[‘Dracula’, ‘Beloved’]
[‘Ulysses’, ‘1984’]
[‘Ulysses’, ‘Dracula’]
[‘Ulysses’, ‘Ulysses’]
[‘Ulysses’, ‘Beloved’]
[‘Beloved’, ‘1984’]
[‘Beloved’, ‘Dracula’]
[‘Beloved’, ‘Ulysses’]
[‘Beloved’, ‘Beloved’]
כפי שאפשר להיווכח מהפלט, הקוד אינו מפיק בדיוק את הזוגות הנדרשים בהגדרת הבעיה. בראש ובראשונה הוא יוצר זוגות שבהם שם ספר מופיע פעמיים. הזוגות האלה נוצרים כיוון שהלולאה הפנימית סורקת את כל שמות הספרים ברשימה books, כולל שם הספר הנסרק בלולאה החיצונית. למשל כשהלולאה החיצונית סורקת את שם הספר ‘1984’, גם הלולאה הפנימית סורקת אותו, ולכן נוצרת הרשימה [‘1984’, ‘1984’]. אפשר לנסות לפתור את הבעיה באופן זה –
books = [‘1984’, ‘Dracula’, ‘Ulysses’, ‘Beloved’]
for book1 in books:
for book2 in books:
if book1 != book2:
print([book1, book2])
כאן התנינו הדפסה של זוג שמות ספרים בשוני בין השמות בזוג. הפעם בפלט לא יהיו רשימות המכילות ערכים שווים –
[[‘1984’, ‘Dracula’],
[‘1984’, ‘Ulysses’],
[‘1984’, ‘Beloved’],
[‘Dracula’, ‘1984’],
[‘Dracula’, ‘Ulysses’],
[‘Dracula’, ‘Beloved’],
[‘Ulysses’, ‘1984’],
[‘Ulysses’, ‘Dracula’],
[‘Ulysses’, ‘Beloved’],
[‘Beloved’, ‘1984’],
[‘Beloved’, ‘Dracula’],
[‘Beloved’, ‘Ulysses’]]
כפי שאפשר להיווכח מהפלט, הקוד עדיין אינו מפיק בדיוק את הזוגות הנדרשים בהגדרת הבעיה: הוא יוצר זוגות זהים מבחינת תכנם, הגם שלא מבחינת סדרם. למשל מודפסים הן הזוג [‘Dracula’, ‘Beloved’] הן הזוג [‘Beloved’, ‘Dracula’]. נראה שתי גישות להימנע מהכפילויות האלה. גישה אחת היא להימָנע מהדפסה של זוג אם כבר הודפס זוג זהה לו מבחינת תכנו. בניסוח כללי יותר הגישה דנן פותרת בעיה זו –
נתון קוד הסורק ערכים באוסף נתון.
יש לזהות אם אחד או יותר מהערכים שנסרקו זהה לערך הנסרק הנוכחי.
כיצד נבצע את הזיהוי הנדרש? דרך אחת היא להכניס כל ערך שכבר נסרק לתוך אוסף ייעודי. קודם שהקוד יבוא לטפל בערך הבא באוסף, הוא יבדוק אם הערך הזה הוכנס לאוסף הייעודי. הנה שלד לקוד המממש גישה זו במקרה שלפנינו –
books = [‘1984’, ‘Dracula’, ‘Ulysses’, ‘Beloved’]
printed = []
for book1 in books:
for book2 in books:
if book1 != book2:
sortedPair = sorted([book1, book2])
if sortedPair not in printed:
print([book1, book2])
printed.append(sortedPair)
>>>
[‘1984’, ‘Dracula’]
[‘1984’, ‘Ulysses’]
[‘1984’, ‘Beloved’]
[‘Dracula’, ‘Ulysses’]
[‘Dracula’, ‘Beloved’]
[‘Ulysses’, ‘Beloved’]
לפני הלולאות יצרנו רשימת עזר בשם printed ואתחלנו אותה לרשימה ריקה. לאחר כל הדפסה של רשימת זוג, הכנסנו רשימה ממוינת של הזוג הזה לרשימה printed. בכל פעם שבאנו להדפיס רשימה של הזוג הבא, בדקנו אם רשימה ממוינת של הזוג הזה עדיין לא הוכנסה לרשימה printed, כלומר אם הזוג הזה טרם הודפס, ורק אם זה המצב הוא הודפס. מדוע הרשימות המוכנסות והנבדקות הן ממוינות? נעיין למשל בשני הזוגות האלה –
[‘Dracula’, ‘Beloved’]
[‘Beloved’, ‘Dracula’]
זוגות אלה שונים מבחינת סדרם אך זהים מבחינת תכנם. לכן יש להדפיס רק אחד מהם. כבר ראינו למעלה כי הזוג [‘Dracula’, ‘Beloved’] הוא הראשון שנסרק, ולכן הוא מודפס. נניח שהוא מוכנס לרשימה printed כפי שהוא, כלומר בלי למיינו. כשנסרק הזוג [‘Beloved’, ‘Dracula’] אין להדפיס אותו. אך כשנבדוק אם הוא קיים ברשימה printed לא נמצא אותו שם (הואיל וההשוואה בין הרשימות נעשית לא רק לפי תכנן כי אם גם לפי סדר הערכים בהן), ולכן בכל זאת נדפיס אותו. כדי שנמצא אותו שם, עלינו להכניס את רשימת הזוג [‘Dracula’, ‘Beloved’]לרשימה printed כשהיא ממוינת, ובנוסף, כשנבוא לבדוק אם רשימת הזוג [‘Beloved’, ‘Dracula’] נמצאת ברשימה printed – לבדוק אותה כשהיא ממוינת, כלומר לבדוק אם הרשימה [‘Dracula’, ‘Beloved’]נמצאת ברשימה printed; או אז נמצא אותה שם, ונמָנע מהדפסתה, כנדרש.
גישה אחרת להתמודדות עם בעיית הכפילויות בהדפסה היא להימנע מראש מיצירתה. בקוד נשיג זאת באמצעות סריקת אינדקסים חלקית. עיינו בקטע הקוד הזה –
books = [‘1984’, ‘Dracula’, ‘Ulysses’, ‘Beloved’]
for i in range(len(books)):
for j in range(i + 1, len(books)):
print([books[i], books[j]])
>>>
[‘1984’, ‘Dracula’]
[‘1984’, ‘Ulysses’]
[‘1984’, ‘Beloved’]
[‘Dracula’, ‘Ulysses’]
[‘Dracula’, ‘Beloved’]
[‘Ulysses’, ‘Beloved’]
הנה טבלת מעקב העוקבת אחר ביצוע הלולאות –
שלא כמו בקוד הקודם, הפעם לולאת ה-for הפנימית לא סרקה את כל הרשימה books. עבור כל אינדקס i שסורקת לולאת ה-for החיצוונית, הלולאה הפנימית סורקת רק חלק מהאינדקסים של הרשימה, כדלקמן –
• עבור i == 0, הלולאה הפנימית מציבה באינדקס j את האינדקסים 1, 2, ו-3, ולכן הודפסו רשימות הזוגות האלה –
[‘1984’, ‘Dracula’]
[‘1984’, ‘Ulysses’]
[‘1984’, ‘Beloved’]
• עבור i == 1, הלולאה הפנימית מציבה באינדקס j את האינדקסים 2, ו-3, ולכן הודפסו רשימות הזוגות האלה –
[‘Dracula’, ‘Ulysses’]
[‘Dracula’, ‘Beloved’]
• עבור i == 2, הלולאה הפנימית מציבה באינדקס j את האינדקס 3, ולכן הודפסה רשימת הזוג הזאת –
[‘Ulysses’, ‘Beloved’]
• ועבור i == 3, הלולאה הפנימית כלל לא תרוץ, כיוון שהפונקציה range תחזיר סדרה ריקה (בצורה מפורשת הזימון שלה הוא range(4,4)). ובאמת אין ליצור זוג שהשם הראשון בו הוא ‘Beloved’ כי כבר הודפסו כל הזוגות המכילים שם זה.
אם כן בניסוח כללי, בפתרון זה אנו סורקים, עבור כל ספר ברשימה books, את כל הספרים הבאים ברשימה אחריו. באופן זה אנחנו מוודאים שלא יווצרו זוגות הזהים מבחינת תכנם.
עד כאן הפתרון לבעיית הדפסת הזוגות. נעבור מכאן לפתרון הבעיה המקורית, דהיינו הדפסת השלשות. נציע שני פתרונות, וכל אחד מהם הוא שכתוב של פתרון לבעיית הזוגות. הנה פתרון המבוסס על סריקת אינדקסים חלקית –
books = [‘1984’, ‘Dracula’, ‘Ulysses’, ‘Beloved’]
for i in range(len(books)):
for j in range(i + 1, len(books)):
for k in range(j + 1, len(books)):
print([books[i], books[j], books[k]])
>>>
[‘1984’, ‘Dracula’, ‘Ulysses’]
[‘1984’, ‘Dracula’, ‘Beloved’]
[‘1984’, ‘Ulysses’, ‘Beloved’]
[‘Dracula’, ‘Ulysses’, ‘Beloved’]
טבלת מעקב זו עוקבת אחר ביצוע הלולאות בקוד האחרון –
עקרון הפעולה כאן זהה לעקרון הפעולה בהדפסת הזוגות, והוא מבטיח שלא ייווצרו שלשות זהות מבחינת תכנן. ואמנם כפי שאפשר לראות בפלט מודפסות כל השלשות המקיימות את הנדרש. ספציפית הוספנו כאן לולאת for שלישית, הסורקת אינדקסים, וסורקת את סדרת האינדקסים שבה האינדקס הראשון הוא זה הבא לאחר האינדקס שסורקת לולאת ה-for הפנימית הראשונה. הנה מעקב מפורט אחר ביצוע הקוד –
• שלשת האינדקסים הראשונה הנסרקת היא i == 0, j == 1, k == 2. נוצרת השלשה הזאת –
[‘1984’, ‘Dracula’, ‘Ulysses’]
• שלשת האינדקסים השניה הנסרקת היא i == 0, j == 1, k == 3. נוצרת השלשה הזאת –
[‘1984’, ‘Dracula’, ‘Beloved’]
כאן מסתיימים הסיבובים של לולאת ה-for הפנימית ביותר, עבור i == 0, j == 1.
• שלשת האינדקסים השלישית הנסרקת היא i == 0, j == 2, k == 3. נוצרת השלשה הזאת –
[‘1984’, ‘Ulysses’, ‘Beloved’]
כאן מסתיימים הסיבובים של לולאת ה-for הפנימית ביותר, עבור i == 0, j == 2.
• שלשת האינדקסים הרביעית הנסרקת היא i == 0, j == 3, k == 4. כאן הלולאה הפנימית ביותר אינה מתבצעת אפילו פעם אחת כיוון שהפונקציה range מחזירה סדרה ריקה (הצורה המפורשת של הזימון הוא range(4, 4)).
כאן מסתיימים הסיבובים של לולאת ה-for הפנימית הראשונה, עבור i == 0.
• שלשת האינדקסים החמשית הנסרקת היא i == 1, j == 2, k == 3. נוצרת השלשה הזאת –
[‘Dracula’, ‘Ulysses’, ‘Beloved’]
• שלשת האינדקסים הששית הנסרקת היא i == 1, j == 3, k == 4. גם כאן הלולאה הפנימית ביותר אינה מתבצעת אפילו פעם אחת כיוון שהפונקציה range מחזירה סדרה ריקה.
כאן מסתיימים הסיבובים של לולאת ה-for הפנימית הראשונה, עבור i == 1.
• שלשת האינדקסים השביעית הנסרקת היא i == 2, j == 3, k == 4. גם כאן הלולאה הפנימית ביותר אינה מתבצעת אפילו פעם אחת כיוון שהפונקציה range מחזירה סדרה ריקה.
כאן מסתיימים הסיבובים של לולאת ה-for הפנימית הראשונה, עבור i == 2.
• שלשת האינדקסים השמינית והאחרונה הנסרקת היא i == 3, j == 4, k == 5. כאן הלולאה הפנימית הראשונה אינה מתבצעת אפילו פעם אחת כיוון שהפונקציה range מחזירה סדרה ריקה.
עד כאן הפתרון ליצירת שלשות שמות הספרים המבוסס על סריקת אינדקסים חלקית. עכשיו נפנה לפתרון המבוסס על שימוש ברשימת עזר. הנה המימוש –
books = [‘1984’, ‘Dracula’, ‘Ulysses’, ‘Beloved’]
printed = []
for book1 in books:
for book2 in books:
for book3 in books:
if book1 != book2 and book2 != book3 and book1 != book3:
sortedTriad = sorted([book1, book2, book3])
if sortedTriad not in printed:
print([book1, book2, book3])
printed.append(sortedTriad)
>>>
[‘1984’, ‘Dracula’, ‘Ulysses’]
[‘1984’, ‘Dracula’, ‘Beloved’]
[‘1984’, ‘Ulysses’, ‘Beloved’]
[‘Dracula’, ‘Ulysses’, ‘Beloved’]
גם כאן הוספנו לולאת for שלישית. כשתי קודמותיה אף היא סורקת את כל הספרים ברשימה books. התנאי הנבדק בהוראת ה-if הוא הרחבה של התנאי שהופיע בהוראה זו בגרסת הקוד שיצרה את כל זוגות השמות: גם כאן הוא בא לוודא שאין ברשימה המודפסת שם של ספר המופיע יותר מפעם אחת. שאר הקוד נסמך על העקרון שהוסבר קודם בנוגע לשימוש ברשימת העזר ולמיון של הרשימות המוכנסות והנבדקות.
