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

תמורות (Permutations)

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

lteq3.png

התמורה הבאה

הצגנו את האלגוריתם שמקבל תמורה כרשימה
lteq4.png
נתונה באורך lteq5.png ומחשב את התמורה הבאה. להלן הצעדים:
  1. מצא את הזוג lteq6.png האחרון שבסדר עולה. אם לא קיים כזה זוג, הגענו לתמורה האחרונה וסיימנו. אחרת lteq7.png הם המציינים (indices) של ה"זוג העולה" lteq8.png האחרון בתמורה.
  2. מצא את המספר האחרון lteq9.png (במקום ה- lteq10.png ) ברשימה כך ש- lteq11.png
  3. החלף בין lteq12.png .
  4. הפוך (היפוך מַרְאָה) את הזנב: lteq13.png .

דוגמא:

נניח lteq14.png . להלן השלבים במציאת התמורה הבאה:
  1. מציאת הזוג העולה האחרון: lteq15.png .
  2. מציאת ה"מחליף" כלומר האחרון שגדול מ- lteq16.png . כאן הוא lteq17.png .
  3. החלפה: lteq18.png .
  4. הפיכת הזנב lteq19.png .

תרגילים

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

חזרה לעמוד האם