תכנות — שיעור 90 11/June/2009    

תמורות (Permutations)

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

התמורה הבאה

1. מצא את הזוג האחרון שבסדר עולה. אם לא קיים כזה זוג, הגענו לתמורה האחרונה וסיימנו. אחרת הם המציינים (indices) של ה"זוג העולה" האחרון בתמורה.
2. מצא את המספר האחרון (במקום ה- ) ברשימה כך ש-
3. החלף בין .
4. הפוך (היפוך מַרְאָה) את הזנב: .

דוגמא:

1. מציאת הזוג העולה האחרון: .
2. מציאת ה"מחליף" כלומר האחרון שגדול מ- . כאן הוא .
3. החלפה: .
4. הפיכת הזנב .

תרגילים

1. השלם תרגילים קודמים.
2. הורד את התכנית nextperm.py והרץ. ממֵש שם את הפונקציה next_permutation(a) שמקבלת רשימה של מספרים a המתארת תמורה, ומחזירה את התמורה הבאה. אם זוהי התמורה האחרונה (מספרים בסדר יורד) אז הפונקציה תחזיר None.
   התכנית הראשית כבר מוכנה ואמורה להדפיס את כל התמורות של גודל נתון.