std::next_permutation شرح التنفيذ

تحسب خوارزمية std::next_permutation التقليب الأكبر التالي من الناحية المعجمية لتسلسل معين. يعد فهم تنفيذها أمرًا بالغ الأهمية لفهم سلوكها.

مخطط الخوارزمية

تتكرر الخوارزمية عبر التسلسل من اليمين إلى اليسار، وتبحث عن "الصاعد" في أقصى اليسار (أي: ، وهو عنصر أصغر من خليفته). إذا لم يتم العثور على تصاعدي، فهذا يعني أن التسلسل في ترتيب تنازلي، وفي هذه الحالة يتم عكس التسلسل للحصول على أصغر التقليب.

خلاف ذلك، تستمر الخوارزمية في العثور على أصغر عنصر في التسلسل إلى اليمين من الصاعد (يسمى "ك"). ثم يتم تبديل هذا العنصر مع الصاعد. أخيرًا، يتم عكس العناصر الموجودة على يمين الصاعد للحفاظ على الترتيب التنازلي. العنصر الحالي الذي يتم فحصه.

j: يشير إلى العنصر الذي يسبقه مباشرة i.

k:
• يشير إلى أصغر عنصر في التسلسل على يمين i عندما يكون i صاعدًا.
• تدفق الحلقة
تتكرر الحلقة حتى أصل إلى بداية التسلسل (البدء). داخل كل تكرار:
• إذا لم يكن i صاعدًا، فإنه يتناقص i وj.

إذا كان i صاعدًا، فإنه يجد أصغر عنصر على يمين i (k )، يستبدلها بـ i، ويعكس كل شيء إلى يمين i.

مثال

فكر في التسلسل {1، 2، 4، 3}.

2. التكرار 1:
i مبدئيًا عند 3. j عند 2. بما أن 3

التكرار 2: k تم العثور على 2. تم تبديل 3 بـ 2. {1, 3, 4, 2}. يتم عكس العناصر الموجودة على يمين 3 (4 و 2). {1, 3, 2, 4}.

التكرار 3:

يتم تقليل i ويتم تقليل j. أنا الآن عند 2. j عند 1. 2 التكرار 4: تم العثور على k ليكون 1. تم تبديل 2 بـ 1. { 1، 2، 4، 3}. يتم عكس العناصر الموجودة على يمين 2 (4 و 3). {1, 2, 3, 4}.
• التكرار 5: يتم تقليل i ويتم تقليل j. أنا الآن عند 1. j في بداية التسلسل. نظرًا لعدم وجود المزيد من الصاعدين، يتم عكس التسلسل. {4، 3، 2، 1}.