תכנות, רקורסיה, מערכים, מחרוזות, עצים בינאריים ורשימות מקושרות
| לפני הקריאה לפונקציה | אחרי הקריאה לפונקציה | ערך החזרה | הסבר |
|---|---|---|---|
| 2 | הפרמוטציה הקטנה ביותר היא והיא שונה מהמחרוזת המקורית ב-2 מקומות (יש להחליף את התו d בתו a ואת התו a בתו d). הפרמוטציה הגדולה ביותר היא והיא שונה מהמחרוזת המקורית ב-4 מקומות (התו היחיד שנשאר במקום ולא מוחלף זה התו c) | ||
| 3 | הפרמוטציה הקטנה ביותר היא והיא שונה מהמחרוזת המקורית ב-4 מקומות (התו היחיד שנשאר במקום ולא מוחלף זה התו z). הפרמוטציה הגדולה ביותר היא והיא שונה מהמחרוזת המקורית ב-3 מקומות. | ||
| 0 | אין צורך לשנות את המחרוזת כיוון שהיא הפרמוטציה הקטנה ביותר והיא דורשת 0 שינויים. |
| קלט | פלט | הסבר |
|---|---|---|
| , | 1 | היא כמעט פרמוטציה של (חסר התו 'a'). |
| , | 3 | תתי המחרוזות באורך 3 של הן: . היא כמעט פרמוטציה של 3 מהן: (חסר התו 'b'), (חסר התו 'b'), (חסר התו 'a'). |
perm_first(lst, k). הפונקציה מקבלת כקלט רשימת מספרים ממוינים שאורכה ומספר שלם אי-שלילי . הפונקציה תחזיר את האיבר הראשון בפרמוטציה ה- בסדר הלקסיקוגרפי של . כלומר, הפונקציה תחזיר את .local_lex(lst, k) שמקבלת כקלט רשימת מספרים ממוינים שאורכה ומספר . הפונקציה תחזיר את הפרמוטציה ה- בסדר הלקסיקוגרפי של . כלומר, הפונקציה תחזיר את .local_lex כפונקציה מעטפת. ניתן להשתמש ב-perm_first. בכלל, הניחו שפעולות אריתמטיות לוקחות זמן (אפילו אם המספרים המעורבים גדולים).local_lex(lst, k) כפונקציה של ו/או . תנו תשובה הדוקה ככל הניתן במונחים אסימפטוטיים () והסבירו תשובתכם בקצרה. הניחו שפעולות אריתמטיות לוקחות זמן (אפילו אם המספרים המעורבים גדולים)."SAAB", הפונקציה תוציא את הפלט הבא (רק 16 מילים ראשונות מופעיות):CountPermutations המקבלת שתי מחרוזות s1 באורך ו-s2 באורך , ומחזירה את מספר האינדקסים ב-s1 בהם מתחילה פרמוטציה של מחרוזת s2.s1 ו-s2 מורכבות מאותיות קטנות באנגלית בלבד.s2 מופיעות 6 פעמים בתוך s1:compose. המתודה מקבלת שתי פרמוטציות self, other ומחזירה פרמוטציה חדשה שהיא ההרכבה .Permutation. פרמוטציה באורך היא פונקציה חד-חד ערכית ועל מהמספרים לעצמם. נייצג פרמוטציה באמצעות רשימה lst באורך : אם אזי lst[i] = j.__init__ ואת מתודת __getitem__.lst. אם הרשימה מתארת פרמוטציה חוקית - שמרו אותה ב-self.perm. אחרת, שמרו None.__getitem__ מקבלת מספר i ומחזירה את .__init__ בזמן O(n) במקרה הגרוע, ללא הגבלה על סיבוכיות הזיכרון.__init__ אין להניח כי הקלט תקין.compose_list אשר מקבלת רשימה lst המכילה אובייקטים מטיפוס Permutation ומחזירה את הרכבת הרשימה.inv אשר מקבלת אובייקט self מטיפוס Permutation ומחזירה את הפרמוטציה ההופכית של self.שאלות תרגול במבוא למדעי המחשב בנושא פרמוטציות ממבחנים של האוניברסיטה הפתוחה, אוניברסיטת תל אביב, אוניברסיטת בר-אילן, הטכניון. השאלות ממוינות לפי רמת קושי, עם פתרונות לבדיקה עצמית - כך שניתן ללמוד מטעויות ולהבין את דרך הפתרון לפני הבחינה. ניתן לאתר שאלות חוזרות ולהריץ מבחני סימולציה ממוקדים בנושא פרמוטציות.