التكرار على التباديل

التقليب في الطول n هو مجموعة مرتبة بدون تكرار الأرقام 1 ، 2 ، ... ، n. على سبيل المثال ، [3 ، 1 ، 2] و [5 ، 4 ، 3 ، 2 ، 1] هي تبديلات ، لكن [1 ، 2 ، 1 ، 3] و [1 ، 2 ، 4] ليست كذلك.

إذا تم تقليل المهمة إلى حقيقة أنه من الضروري التكرار على جميع التباديل للطول n ، فيمكنك استخدام آلية ملائمة في C ++ ، والتي تسمى "next_permutation".

يمكنك قراءة المزيد عنها في & nbsp؛ وثائق ، لكن النقطة هي أن هذه الوظيفة تغير المصفوفة التي تم تمريرها إلى التقليب اللاحق في الترتيب المعجمي (وهو أمر واضح بشكل عام واسمه).

لاستخدام next_permutation ، تحتاج إلى تضمين مكتبة الخوارزمية (على سبيل المثال ، اكتب #include & lt؛ algorithm & gt؛ في بداية البرنامج)

أمثلة: ناقلات arr ؛ arr = {1، 2، 3} ؛ // المصفوفة هي [1 ، 2 ، 3] next_permutation (arr.begin ()، arr.end ()) ، // قم بتمرير المصفوفة بأكملها إلى الوظيفة // المصفوفة هي الآن [1 ، 3 ، 2] arr = {2، 3، 1} ؛ // المصفوفة هي [2 ، 3 ، 1] next_permutation (arr.begin ()، arr.end ()) ، // قم بتمرير المصفوفة بأكملها إلى الوظيفة // المصفوفة هي الآن [3 ، 1 ، 2] next_permutation (arr.begin () + 1، arr.begin () + 3) ، // من الممكن تطبيق دالة على جزء من مصفوفة ، ولكن نادرًا ما تكون هناك حاجة إلى ذلك عمليًا // المصفوفة هي الآن [3 ، 2 ، 1]
في هذه الحالة ، تحتوي الوظيفة على قيمة إرجاع منطقية تكون صحيحة إذا تم إنشاء التقليب التالي وخطأ إذا لم يكن هناك تالي (الحالة التي يتم فيها تمرير الحد الأقصى للتبديل في الترتيب المعجمي إلى الوظيفة).
هذا يجعل من الممكن استخدام الوظيفة في حلقة ، مما سيسمح لنا بالتكرار عبر جميع التباديل مرة واحدة. بسبب الفهرسة 0 ، من الناحية العملية ، غالبًا ما يكون العمل مع تبديل الأرقام من 0 إلى n - 1 أكثر ملاءمة ، على الرغم من أن التقليب يحتوي رسميًا على أرقام من 1 إلى n. لكن لحسن الحظ ، هذا لا يؤدي إلى تراكبات إضافية في الكود ، لأن تم تكييف وظيفة next_permutation مع التباديل ذي الصفر المفهرس (وحتى العناصر المكررة في المصفوفة ، ولكن يمكنك معرفة المزيد بنفسك).

بشكل عام ، يبدو رمز التكرار على جميع التباديل كما يلي: & nbsp؛ إنتن. // حجم التقليب متجه perm (n) ؛ // perm هي اختصار لـ "التقليب" ، أي "التقليب" لـ (int i = 0 ؛ i & lt ؛ n ؛ i ++) بيرم [i] = أنا ؛ // تهيئة التقليب الأولي 0 ، 1 ، ... ، ن - 1 يفعل { // داخل الحلقة نقوم بمعالجة التقليب الحالي } while (next_permutation (perm.begin ()، perm.end ())) ؛ // إذا لم يكن هناك تبديل تالٍ ، فقم بإنهاء الحلقة

يعمل هذا الرمز في O (n! * f (n)) ، حيث f (n) هو الوقت الذي تستغرقه في معالجة تبديل واحد معين.