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

التراجع باستخدام مصفوفة مستخدمة

الفكرة

املأ 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!، لكنها تعرض [3, 2, 1] قبل [3, 1, 2] للقيمة [1, 2, 3].
التحقق من استخدام قيمة عبر البحث في 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]]