Permutations

+10

מקבלים רשימה nums של מספרים שלמים שונים. החזירו את כל הסדרים האפשריים של הערכים האלה, כשכל אחד מהם הוא רשימה שמשתמשת בכל ערך בדיוק פעם אחת, כך ש־n ערכים נותנים n! סדרים. הציגו אותם בסדר לקסיקוגרפי: השוו בין שני סדרים מיקום אחר מיקום, וההבדל הראשון הוא שיכריע. עבור [1, 2, 3], הסדר הזה מציב את [1, 2, 3] ראשון ואת [3, 2, 1] אחרון.

פונקציה

permute(nums: integer-array) → integer-2d-array

numsinteger-array: הערכים, כולם שונים, בכל סדר
מחזירהinteger-2d-array: כל הסידורים האפשריים של הערכים, בסדר לקסיקוגרפי

אילוצים

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
כל הערכים ב־nums שונים.
nums יכולים להופיע בכל סדר.

דוגמאות

קלט: nums = [3, 1, 2]
פלט: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
הסבר: לשלושה ערכים יש 3! = 6 סידורים. לאחר מיון, הערכים הם 1, 2, 3, ולכן הסידורים שמתחילים ב־1 מופיעים ראשונים, ו־[1, 2, 3] מופיע לפני [1, 3, 2] כי 2 קטן מ־3 במיקום השני. סדר הקלט אינו משנה.

קלט: nums = [2, -1]
פלט: [[-1, 2], [2, -1]]
הסבר: אפשר לכתוב שני ערכים בשני סדרים. [-1, 2] מופיע ראשון כי ‎-1 קטן מ־2.

+13 בדיקות נסתרות בשליחה

שאלת המשך

בהינתן סדר אחד, האם תוכל ליצור את הסדר הבא בסדר לקסיקוגרפי במקום, בזמן O(n) ובשימוש ב־O(1) מקום נוסף?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

לרשימה של n ערכים שונים יש n! סידורים, 720 עבור שישה ערכים, והתשובה חייבת לפרט את כולם, לכן נדרשת עבודה של לפחות n × n!. האתגר הוא לבנות כל סידור פעם אחת ולפלוט אותם בסדר לקסיקוגרפי. חיפוש עם חזרה על פני הערכים הממוינים, תוך ניסיון תמיד של הערך הקטן ביותר שעדיין לא נעשה בו שימוש תחילה, עושה את שני הדברים בו-זמנית.

הכניסו לכל אחד מהפערים, ואז מיינו

האינטואיציה

בנו את הסדרים, ערך אחד בכל פעם. כשאין ערכים, יש סדר אחד: הרשימה הריקה. כדי להוסיף את הערך 3 לסדר [1, 2], הכניסו אותו לכל אחד משלושת המקומות הפנויים: [3, 1, 2], [1, 3, 2] וגם [1, 2, 3]. עשו זאת עבור כל סדר שיש לכם, והסדרים של k ערכים יהפכו לסדרים של k+1 ערכים.

כל סדר של k+1 ערכים נבנה בדיוק פעם אחת: הוציאו ממנו את הערך החדש ביותר, ותקבלו את הסדר היחיד שממנו הוא נבנה, בעוד שהמיקום של הערך החדש ביותר מציין את המקום הפנוי. לכן מספר הסדרים הוא 1, 2, 6, 24, ו-n ערכים נותנים n! סדרים.

הם לא מתקבלים בסדר הנדרש. עבור [1, 2, 3] הסדר הראשון שנבנה הוא [3, 2, 1], ולכן בסוף צריך למיין לפי השוואה של כל מיקום ומיקום. המיון הזה הוא החלק היקר: כדי למיין n! סדרים צריך בערך n! × log(n!) השוואות, ובכל אחת מהן קוראים עד n ערכים. עבור שישה ערכים מדובר בכ-720 × 9.5 × 6, כלומר כ-41,000 קריאות. השיטה גם שומרת בזיכרון דור שלם של סדרים בזמן שהיא בונה את הדור הבא.

אלגוריתם

מתחילים ברשימה שמכילה סדר אחד ריק.
עבור כל ערך ב־nums, בונים רשימה חדשה: עבור כל סדר שנוצר עד כה וכל מרווח מ־0 ועד לאורך שלו, מעתיקים את הסדר כשהערך מוכנס למרווח הזה.
מחליפים את הרשימה הישנה בחדשה.
ממיינים את הסדרים לפי מיקום ומחזירים אותם.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

חזרה לאחור באמצעות מערך used

האינטואיציה

מלאו n משבצות משמאל לימין. למשבצת הראשונה יש n מועמדים, לשנייה n-1, וכך הלאה — ומכאן מגיע n!. אפשר לשרטט את הבחירות האלה כעץ: השורש הוא נתיב ריק, כל קשת מוסיפה ערך נוסף, וכל עלה, בעומק n, הוא סדר סופי אחד. עבור הערכים הממוינים 1, 2, 3, לשורש יש את הילדים [1], [2] ו-[3]; ל-[1] יש את הילדים [1, 2] ו-[1, 3]; לכל אחד מהם יש עלה אחד.

חיפוש עם חזרה עובר בעץ הזה בעזרת path משותף אחד ודגל used לכל ערך. בכל צומת, הלולאה עוברת על הערכים ומדלגת על אלה שכבר בשימוש. עבור כל ערך פנוי היא בוחרת אותו (מסמנת אותו כבשימוש ומוסיפה אותו), חוקרת (קוראת לעצמה ברקורסיה לעומק של רמה אחת נוספת), ואז מבטלת את הבחירה (מסירה אותו ומסמנת אותו כפנוי). שלב ביטול הבחירה משחזר בדיוק את המצב שהיה ללולאה קודם, כך שהערך הבא נבדק מאותו צומת. נתיב באורך n הוא עלה: שמרו עותק וחזרו.

הסדר מתקבל מעצמו. הלולאה מנסה תחילה את הערך הפנוי הקטן ביותר, והמעבר בעץ מסיים כל סידור שמתחיל בקידומת נתונה לפני שהוא משנה את הקידומת הזאת. לכן כל הסידורים שמתחילים ב-1 מופיעים לפני כל סידור שמתחיל ב-2, וביניהם [1, 2, ...] מופיע לפני [1, 3, ...]. זהו סדר לקסיקוגרפי. זו גם הסיבה שממיינים תחילה את nums: הלולאה מתקדמת לפי אינדקס, ולכן האינדקסים חייבים להיות מסודרים לפי ערך.

בעץ יש בערך e × n! צמתים (e הוא בערך 2.72), וכל אחד מהם מריץ לולאה באורך n, ולכן זמן הריצה הוא O(n × n!), באותו סדר גודל כמו מספר התשובות. מלבד הפלט, הנתיב, הדגלים ומחסנית הקריאות מכילים כל אחד לכל היותר n איברים.

אלגוריתם

מיינו את הערכים וצרו מערך used של n דגלים שערכם false.
כתבו את explore(). אם path מכיל n ערכים, הוסיפו עותק לתוצאה והחזירו.
אחרת, עבור כל אינדקס i מ-0 עד n-1 שהערך שלו פנוי: סמנו אותו כמשומש והוסיפו את values[i] (בחירה), קראו ל-explore() (חקירה), ואז הסירו אותו וסמנו אותו כפנוי (ביטול הבחירה).
קראו ל-explore() פעם אחת והחזירו את התוצאה.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

מלכודות ומקרי קצה

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

תיעוד של path במקום עותק שלו. כל n! הרשומות מסתיימות כאותה רשימה, והיא ריקה לאחר שהמעבר מסתיים.
ביטול של רק חצי מבחירה. אם מסירים את הערך אבל משאירים את used[i] מסומן, הערך הזה לא יופיע שוב בענף מאוחר יותר, ויתקבלו פחות מ-n! תמורות.
אי-מיון של nums תחילה. המעבר עדיין מוצא כל תמורה, אבל הן מופיעות לפי סדר הקלט, ולכן הקלט [3, 1, 2] יופיע ראשון.
שימוש בשיטת ההחלפה (החלפת nums[start] בכל מיקום מאוחר יותר, ביצוע קריאה רקורסיבית והחלפה חזרה) בלי מיון סופי. השיטה מוצאת את כל n! התמורות, אבל עבור [1, 2, 3] היא מציגה את [3, 2, 1] לפני [3, 1, 2].
בדיקה אם נעשה שימוש בערך באמצעות חיפוש ב-path. זה עובד כאן רק משום שהערכים שונים, והבדיקה עולה n בכל שלב. דגל לכל אינדקס פועל בזמן O(1) ועובד גם כאשר ערכים חוזרים.

שאלות נפוצות4

כמה תמורות יש לרשימה של n איברים שונים?

n!, נקרא n עצרת: n אפשרויות למקום הראשון, n-1 לשני, ועד אחת לאחרון, כשהכול מוכפל יחד. שלושה ערכים נותנים 6 סידורים, שישה נותנים 720, ועשרה כבר נותנים 3,628,800, ולכן בבעיות תמורה שומרים על n קטן.

מהי סיבוכיות הזמן של יצירת כל התמורות?

O(n × n!). יש n! סדרים, וכתיבה של כל אחד מהם דורשת n צעדים, ולכן שום שיטה לא יכולה להיות יעילה יותר כשהיא צריכה להחזיר את כולם. חיפוש עם חזרה מגיע לחסם הזה, ובנוסף לפלט הוא זקוק ל־O(n) מקום עבור המסלול הנוכחי, הסימונים שמציינים אילו איברים כבר שימשו והקריאות הרקורסיביות.

למה חיפוש עם חזרה לאחור יוצר תמורות בסדר לקסיקוגרפי?

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

איך יוצרים תמורות כשהקלט מכיל כפילויות?

מיינו את הערכים, ובכל מיקום דלגו על ערך ששווה לערך שלפניו, כאשר העותק הקודם הזה אינו בשימוש: i > 0, values[i] == values[i-1] וגם !used[i-1]. כך הערכים השווים יופיעו בסדר המקורי שלהם, ולכן כל סידור ייחודי ייבנה פעם אחת.

Python

def permute(nums):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [3, 1, 2]

צפוי

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]