Next Permutation

Q: ما التعقيد الزمني لـ Next Permutation؟

O(n) . يحدّد مسحٌ واحد من اليمين نقطة الارتكاز، ويعثر مسحٌ ثانٍ على القيمة التي ستُبادَل بها، ثم يعكس قلبٌ واحد اللاحقة لإصلاحها. الذاكرة الإضافية هي O(1) ، لأن كل شيء يحدث داخل المصفوفة.

متوسطالمصفوفات والسلاسل النصية مؤشران

+10

تحصل على مصفوفة من الأعداد الصحيحة nums، وقد تتكرر القيم. تخيّل جميع الترتيبات المختلفة لهذه القيم، مرتبةً وفق الترتيب القاموسي: قارن بين ترتيبين عند أول فهرس يختلفان فيه، ويأتي أولًا الترتيب الذي تكون قيمته أصغر عند ذلك الموضع. أعد الترتيب الذي يأتي مباشرةً بعد nums في ذلك الترتيب.

إذا كان nums بالفعل أكبر ترتيب، فلا يوجد ترتيب يأتي بعده: أعد أصغر ترتيب، وهو القيم مرتبة تصاعديًا. اسعَ إلى تحقيق زمن O(n) وذاكرة إضافية O(1).

الدالة

nextPermutation(nums: integer-array) → integer-array

numsinteger-array: الترتيب الحالي للقيم
تُرجعinteger-array: الترتيب التالي حسب الترتيب المعجمي، أو القيم مرتبةً تصاعديًا إذا كانت nums هي الأكبر

القيود

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

أمثلة

المدخلات: nums = [2, 5, 4, 1]
المخرجات: [4, 1, 2, 5]
الشرح: الذيل 5, 4, 1 يتناقص، لذا يجب أن يزداد العدد 2 الذي يسبقه. أصغر قيمة في الذيل أكبر من 2 هي 4؛ ضعها في مكانه ورتّب الباقي تصاعديًا: [4, 1, 2, 5].

المدخلات: nums = [3, 2, 2, 1]
المخرجات: [1, 2, 2, 3]
الشرح: المصفوفة بأكملها تتناقص، لذا فهذا هو الترتيب الأكبر للعناصر 3 و2 و2 و1. تلتف الإجابة لتعود إلى الأصغر، [1, 2, 2, 3].

المدخلات: nums = [1, 5, 1]
المخرجات: [5, 1, 1]
الشرح: يجب أن تكبر الـ1 الأولى. أما الـ1 الأخيرة فهي مساوية لها، وليست أكبر منها، لذا فالقيمة الوحيدة التي يمكن أن تحل محلها هي 5، وهذا يعطينا [5, 1, 1].

سؤال إضافي

كيف يمكنك العثور على الترتيب السابق بدلاً من ذلك، أي الترتيب الذي يأتي مباشرةً قبل nums حسب الترتيب المعجمي؟

الحل

يكون اللاحقة المتناقصة قد بلغت بالفعل أكبر قيمة تسمح بها عناصرها، لذا يغيّر الترتيب التالي قيمة العنصر الذي يسبقها مباشرةً، وهو المحور. زد قيمة المحور بأصغر مقدار ممكن، ثم اجعل اللاحقة بأصغر قيمة ممكنة. يتطلب ذلك مسحين من اليمين وعملية عكس واحدة داخل المصفوفة.

ترتيب القوائم

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

أنشئ الترتيبات بالبحث أولًا في العمق انطلاقًا من القيم المرتبة، مع تجربة أصغر قيمة غير مستخدمة دائمًا أولًا. ينتج عن ذلك ترتيبها ترتيبًا معجميًا، لذا فإن أول ترتيب أكبر تمامًا من nums هو الإجابة؛ وإن لم يوجد، فأعِد القيم المرتبة. تؤدي القيم المكررة إلى إنشاء بعض الترتيبات مرتين، كما في 115، 151، 115، 151، 511، 511 للقائمة [1, 1, 5]، لكن النسخة المكررة لا تفعل سوى تكرار ترتيب أُنشئ من قبل، لذا يظل أول ترتيب أكبر هو التالي.

يزداد العدد وفقًا لـ n!: فهناك 479,001,600 ترتيبًا لـ 12 قيمة متميزة.

الخوارزمية

رتّب نسخة من nums في pool.
أنشئ الترتيبات باستخدام البحث بالعمق أولًا، مع اختيار العناصر غير المستخدمة من pool من اليسار إلى اليمين.
عند اكتمال ترتيب، قارنه مع nums موضعًا بموضع.
أعِد أول ترتيب يكون أكبر من nums.
إذا لم يكن أي ترتيب أكبر، فأعِد pool.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

اعثر على المحور، بدّل، واعكس اللاحقة

الفكرة

المحور هو أول قيمة من اليمين تكون أصغر من جارتها اليمنى: القيمة 2 في [2, 5, 4, 1]. وهو الموضع الأيمن الذي يمكن زيادته، وزيادة أبعد موضع ممكن إلى اليمين تُبقي الزيادة في حدها الأدنى.

بدّل المحور بأصغر قيمة في اللاحقة تكون أكبر منه تمامًا. اللاحقة تنازلية، لذا فهذه هي القيمة الأكبر من المحور والأبعد إلى اليمين: 4، فنحصل على [4, 5, 2, 1]. تظل اللاحقة تنازلية، لأن موضع المحور القديم يناسب القيمة 4. وبما أن المقدمة أصبحت الآن أكبر، ينبغي أن تكون اللاحقة أصغر ما يمكن، بترتيب تصاعدي، وعكس سلسلة تنازلية يحقق ذلك: [4, 1, 2, 5].

عند عدم وجود محور، تكون المصفوفة هي الترتيب الأكبر، وعكسها بالكامل يعطي الترتيب الأصغر. كل خطوة عبارة عن مسح أو عكس واحد: زمن O(n) وذاكرة O(1)، مع أن إصدار R يعيد نسخة بحجم O(n).

الخوارزمية

عيّن i إلى n-2 وحرّكه إلى اليسار ما دام nums[i] ≥ nums[i + 1].
إذا كان i ≥ 0، فعيّن j إلى n-1 وحرّكه إلى اليسار ما دام nums[j] ≤ nums[i]، ثم بدّل nums[i] وnums[j].
اعكس الجزء من i + 1 إلى النهاية باستخدام مؤشرين يتحركان باتجاه بعضهما.
أعِد nums.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

أخطاء شائعة وحالات حدّية

استخدام > بدلًا من ≥ في البحث عن المحور. في [3, 2, 2, 1] لا يُعد الزوج 2, 2 ارتفاعًا، والتوقف عنده يختار محورًا لا يمكن أن ينمو.
التبديل مع قيمة تساوي المحور. في [1, 5, 1] لا يغيّر تبديل العددين 1 شيئًا؛ ابحث عن قيمة أكبر تمامًا.
التبديل مع أكبر قيمة في اللاحقة. في [2, 5, 4, 1] يؤدي ذلك إلى وضع 5 في المقدمة وتجاوز كل ترتيب يبدأ بـ 4.
تجاوز حالة عدم وجود محور. يجب أن يعود الترتيب الأكبر مرتبًا، وذلك بعكس المصفوفة بأكملها.
في Rust، يؤدي بدء فهرس usize عند n-2 إلى حدوث ذعر عندما تكون n = 1، كما أن الانتقال يسارًا متجاوزًا 0 يؤدي إلى حدوث ذعر عندما لا يوجد محور. استخدم فهرسًا ذا إشارة أو ابدأ العد من 1.

أسئلة شائعة3

ما التعقيد الزمني لـ Next Permutation؟

O(n). يحدّد مسحٌ واحد من اليمين نقطة الارتكاز، ويعثر مسحٌ ثانٍ على القيمة التي ستُبادَل بها، ثم يعكس قلبٌ واحد اللاحقة لإصلاحها. الذاكرة الإضافية هي O(1)، لأن كل شيء يحدث داخل المصفوفة.

لماذا تعكس اللاحقة بدلًا من ترتيبها؟

بعد التبديل، يظل الجزء اللاحق تنازليًا، لذا فإن عكسه يرتبه بالفعل ترتيبًا تصاعديًا. يستغرق العكس O(n)؛ أما الترتيب فيعطي النتيجة نفسها في O(n log n).

هل تعمل Next Permutation مع القيم المكررة؟

نعم، ما دام كلا الشرطين يعاملان القيم المتساوية على أنها غير أكبر. يتجاوز البحث عن المحور العناصر المجاورة المتساوية باستخدام ≥، ويتجاوز البحث عن عنصر التبديل القيم المساوية للمحور باستخدام ≤. عندها تصبح [1, 5, 1] هي [5, 1, 1]، وهو الترتيب المميز التالي.

def nextPermutation(nums):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

وسيط

nums = [2, 5, 4, 1]

الإخراج المتوقع

[4, 1, 2, 5]