خوارزمية Johnson-Trotter لتوليد التباديل: شرح مبسّط بمثال متتبَّع
خوارزمية Johnson-Trotter (وتُعرف أيضًا باسم Steinhaus–Johnson–Trotter أو اختصارًا SJT) هي طريقة لتوليد جميع التباديل الممكنة لمجموعة من العناصر، لكن ميزتها الحقيقية أنها تنتقل من تبديل إلى الذي يليه عبر مبادلة عنصرين متجاورين فقط في كل خطوة. هذا كل جوهرها: بدلًا من إعادة ترتيب القائمة بالكامل في كل مرة، تكفي حركة صغيرة واحدة. وهذا ما يجعلها مثالية عندما تكون كل عملية تبديل مكلفة، لأنك تدفع أقل تغيير ممكن بين حالتين متتاليتين.
توضيح سريع للمصطلح: كلمة «تباديل» هنا تعني permutations، أي كل الترتيبات الممكنة للعناصر. الخوارزمية لا «تحذف المكرر»؛ هي ببساطة تمرّ على العدد الكامل من الترتيبات وهو n! ترتيبًا لمجموعة من n عنصر، لكن بترتيب ذكي يجعل الفرق بين كل ترتيب والذي يليه أدنى ما يمكن.
الفكرة الأساسية: العنصر «المتحرك» والاتجاه
لكل عنصر في القائمة سهمٌ يشير إما لليسار أو لليمين. في البداية تشير كل الأسهم إلى اليسار.
نقول إن عنصرًا «متحرك» (mobile) إذا كان الجار الذي يشير إليه سهمه أصغر منه. مثلًا العنصر 3 المتّجه يسارًا يكون متحركًا إذا كان جاره الأيسر رقمًا أصغر من 3. أما العنصر الواقع على الحافة والمتّجه نحو الخارج فلا يمكن أن يكون متحركًا لعدم وجود جار في اتجاهه.
خطوات الخوارزمية
- ابدأ بالترتيب التصاعدي
1 2 3 … nمع توجيه كل الأسهم إلى اليسار. - سجّل هذا الترتيب كأول تبديل.
- طالما يوجد عنصر متحرك واحد على الأقل، كرّر:
- ابحث عن أكبر عنصر متحرك (وليكن k).
- بادِله مع الجار المجاور له في اتجاه سهمه.
- اعكس اتجاه سهم كل عنصر أكبر من k.
- سجّل الترتيب الجديد.
- عندما لا يبقى أي عنصر متحرك، تكون قد ولّدت كل التباديل وتتوقف الخوارزمية.
نصيحة عملية: القاعدة التي يخطئ فيها كثيرون هي «اعكس اتجاه العناصر الأكبر من k». لا تعكس اتجاه k نفسه، ولا العناصر الأصغر منه، بل فقط ما هو أكبر منه. نسيان هذه الخطوة يجعل الخوارزمية تتوقف مبكرًا قبل توليد كل التباديل.
مثال متتبَّع خطوة بخطوة للمجموعة {1, 2, 3}
نرمز لاتجاه السهم بقوسٍ صغير: ‹ يسار و› يمين.
| # | الترتيب | العنصر الأكبر المتحرك | الناتج |
|---|---|---|---|
| 1 | ‹1 ‹2 ‹3 | 3 (يسار) | 1 3 2 |
| 2 | ‹1 ‹3 ‹2 | 3 (يسار) | 3 1 2 |
| 3 | ‹3 ‹1 ‹2 | 2 (يسار) | 3 2 1 + عكس اتجاه 3 |
| 4 | ›3 ‹2 ‹1 | 3 (يمين) | 2 3 1 |
| 5 | ‹2 ›3 ‹1 | 3 (يمين) | 2 1 3 |
| 6 | ‹2 ‹1 ›3 | لا يوجد | توقّف |
الناتج النهائي بالترتيب: 123 ← 132 ← 312 ← 321 ← 231 ← 213. لاحظ أن كل ترتيب يختلف عن سابقه بمبادلة رقمين متجاورين فقط، تمامًا كما وعدت الخوارزمية.
أين تُستخدم فعلًا؟ وتصحيح مفهوم شائع
القيمة الحقيقية لـ SJT ليست مجرد «توليد التباديل»، فهناك خوارزميات أبسط لذلك، بل في أنها تولّدها بترتيب «الحد الأدنى من التغيير» (نوع من رموز غراي Gray code على التباديل). هذا يفيد في:
- الاختبار الشامل: تجربة كل ترتيبات المدخلات على برنامج مع أقل تعديل بين حالة واختبار والذي يليه.
- المسائل التوافقية: عندما يكون بناء الحالة الجديدة من الصفر مكلفًا، فالمبادلة الواحدة أرخص بكثير.
- العتاد والأنظمة الميكانيكية: حيث تكون كل «حركة» فعلية ومكلفة، مثل ترتيب الأجراس في فن قرع النواقيس (change ringing) الذي أُلهمت منه الفكرة أصلًا.
تصحيح مهم: تروّج بعض الصفحات لأن Johnson-Trotter «خوارزمية تشفير». هذا غير دقيق. هي ليست نظام تشفير ولا تُوفّر أمانًا بحد ذاتها؛ أقصى ما يمكن هو استخدامها كخطوة مساعدة لتوليد ترتيبات ضمن نظام أكبر. لا تعتمد عليها كوسيلة حماية.
الأداء والتعقيد
عدد التباديل هو n! دائمًا، وهو ما يجعل توليد الكل غير عملي للأعداد الكبيرة (مثلًا 12! يتجاوز 479 مليونًا). النسخة المباشرة من الخوارزمية تحتاج في كل خطوة إلى مسحٍ للبحث عن أكبر عنصر متحرك بتكلفة O(n)، لكن توجد نسخة محسَّنة (تحسين إيفن) تنتقل بين تبديل وآخر بزمنٍ ثابت O(1) مُطفّأ. اختر النسخة البسيطة للتعلّم والوضوح، والمحسَّنة إذا كان الأداء حرجًا.
الأسئلة الشائعة
ما الفرق بين Johnson-Trotter وخوارزمية Heap؟ كلتاهما تولّدان كل التباديل، لكن Heap أبسط وأسرع برمجيًا وتبادل عنصرين (ليسا بالضرورة متجاورين)، بينما تضمن SJT أن يكون التغيير دائمًا مبادلة متجاورة واحدة. إن كنت تحتاج خاصية «الحد الأدنى من التغيير» فاختر SJT، وإلا فـ Heap عادةً كافية.
هل تعمل مع عناصر مكرّرة؟ النسخة الأساسية مصمّمة لعناصر مميّزة (مثل أرقام مختلفة). للتعامل مع التكرار تحتاج تعديلات إضافية، وإلا ستولّد ترتيبات تبدو مكرّرة.
هل يمكن تطبيقها على حروف أو كائنات بدل الأرقام؟ نعم. الأرقام مجرد أداة لتحديد «الأكبر». يكفي أن ترتّب العناصر حسب أولوية معيّنة (كالترتيب الأبجدي) ثم تطبّق القاعدة نفسها.
لماذا نبدأ دائمًا من الترتيب التصاعدي؟ لأنه يضمن توليد كل التباديل مرة واحدة دون تكرار أو نقص. البدء من ترتيب آخر ممكن نظريًا، لكنه يعقّد ضمان التغطية الكاملة.