תכנות
—
שיעור 90
11/June/2009
תמורות
(Permutations)
תיארנו איך ליצור את כל התמורות של סדרה סופית של מספרים.
התמורה הראשונה היא בסדר מספרים עולה, והאחרונה בסדר יורד.
לדוגמא
התמורות של המספרים
.
התמורה הבאה
הצגנו את האלגוריתם שמקבל תמורה כרשימה
נתונה באורך
ומחשב את התמורה הבאה.
להלן הצעדים:
-
מצא את הזוג
האחרון שבסדר עולה.
אם לא קיים כזה זוג, הגענו לתמורה האחרונה וסיימנו.
אחרת
הם המציינים
(indices)
של ה"זוג העולה"
האחרון בתמורה.
-
מצא את המספר האחרון
(במקום ה-
)
ברשימה כך ש-
-
החלף בין
.
-
הפוך (היפוך מַרְאָה) את הזנב:
.
דוגמא:
נניח
.
להלן השלבים במציאת התמורה הבאה:
-
מציאת הזוג העולה האחרון:
.
-
מציאת ה"מחליף" כלומר האחרון שגדול מ-
.
כאן הוא
.
-
החלפה:
.
-
הפיכת הזנב
.
תרגילים
-
השלם תרגילים קודמים.
-
הורד את התכנית
nextperm.py
והרץ.
ממֵש שם את הפונקציה
next_permutation(a)
שמקבלת רשימה של מספרים a המתארת תמורה, ומחזירה את התמורה הבאה.
אם זוהי התמורה האחרונה (מספרים בסדר יורד) אז הפונקציה תחזיר
None
.
התכנית הראשית כבר מוכנה ואמורה להדפיס את כל התמורות של גודל נתון.
חזרה לעמוד האם