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

تُنتج خوارزمية هيب جميع التباديل الممكنة لـ n عنصرًا. وقد اقترحها بي آر هيب لأول مرة عام 1963. ^{[ 1 ]} تُقلل الخوارزمية من حركة العناصر: إذ تُنتج كل تبديل من التبديل السابق عن طريق تبديل زوج واحد فقط من العناصر؛ بينما تبقى العناصر المتبقية n − 2 دون تغيير. وفي مراجعة أجراها روبرت سيدجويك عام 1977 لخوارزميات توليد التباديل، خلص إلى أنها كانت آنذاك الخوارزمية الأكثر فعالية لتوليد التباديل باستخدام الحاسوب. ^{[ 2 ]}

إن سلسلة تباديل n عنصرًا التي تولدها خوارزمية هيب هي بداية سلسلة تباديل n + 1 عنصرًا. لذا، توجد سلسلة واحدة لانهائية من التباديل التي تولدها خوارزمية هيب (السلسلة A280318 في OEIS ) .

لمجموعة${\displaystyle C}$تحتوي الكومة على n عنصرًا مختلفًا، وقد وجدت طريقة منهجية لاختيار زوج من العناصر في كل خطوة لتبديلها من أجل إنتاج كل تبديل ممكن لهذه العناصر مرة واحدة بالضبط.

تُعرف خوارزمية هيب، التي تُوصف بشكل متكرر بأنها طريقة التناقص والتغلب ، بأنها تعمل في كل خطوة على${\displaystyle k}$العناصر الأولية للمجموعة. في البداية${\displaystyle k=n}$وبعد ذلك${\displaystyle k<n}$تُنتج كل خطوة${\displaystyle k!}$التباديل التي تنتهي بنفس${\displaystyle nk}$العناصر النهائية. يتم ذلك عن طريق استدعاء نفسه مرة واحدة باستخدام${\displaystyle k{\text{th}}}$العنصر دون تغيير ثم${\displaystyle k-1}$أوقات مع (${\displaystyle k{\text{th}}}$) عنصر يتم استبداله بكل عنصر من العناصر الأولية${\displaystyle k-1}$العناصر. تعمل الاستدعاءات المتكررة على تعديل العناصر الأولية${\displaystyle k-1}$يلزم وجود عناصر وقاعدة في كل تكرار لاختيار العنصر الذي سيتم استبداله بالعنصر السابق. تنص طريقة الكومة على أنه يمكن إجراء هذا الاختيار بناءً على زوجية عدد العناصر التي يتم العمل عليها في هذه الخطوة.${\displaystyle k}$إذا كان العدد زوجيًا، فسيتم استبدال العنصر الأخير بشكل متكرر مع كل فهرس عنصر.${\displaystyle k}$في حالة الشذوذ، يتم دائمًا استبدال العنصر الأخير بالعنصر الأول.

// إخراج k! من تباديل المصفوفة A حيث يتم تبديل العناصر k الأولى بجميع الطرق. // للحصول على جميع تباديل A، استخدم k := طول A. // // إذا كان k > طول A، فسيتم محاولة الوصول إلى A خارج النطاق. // إذا كان k <= 0، فلن يكون هناك أي إخراج (المصفوفة الفارغة ليس لها تباديل) procedure permutations ( k : عدد صحيح , A : مصفوفة من أي نوع ) : if k = 1 then output ( A ) else // تباديل مع تثبيت العنصر الأخير permutations ( k - 1 , A ) // تباديل مع تبديل العنصر الأخير for i := 0 ; i < k - 1 ; i += 1 do if k is even then swap ( A [ i ] , A [ k - 1 ]) else swap ( A [ 0 ] , A [ k - 1 ]) end if permutations ( k - 1 , A ) end for end if

يمكن أيضًا كتابة الخوارزمية بصيغة غير تكرارية. ^{[ 3 ]}

الإجراء permutations ( n : عدد صحيح ، A : مصفوفة من أي نوع ) : // c هو ترميز لحالة المكدس. // c[k] يرمز إلى عداد حلقة for عند استدعاء permutations(k + 1, A) c : مصفوفة من الأعداد الصحيحةfor i := 0 ; i < n ; i += 1 do c [ i ] := 0 end foroutput ( A ) // يعمل i بشكل مشابه لمؤشر المكدس i := 1 ; while i < n do if c [ i ] < i then if i is even then swap ( A [ 0 ] , A [ i ]) else swap ( A [ c [ i ]] , A [ i ]) end if output ( A ) // تم التبديل، مما أنهى حلقة while. قم بمحاكاة زيادة عداد حلقة while c [ i ] += 1 // قم بمحاكاة الاستدعاء التكراري الذي يصل إلى حالة الأساس عن طريق نقل المؤشر إلى نظير حالة الأساس في المصفوفة i := 1 else // انتهى استدعاء permutations(i+1, A) حيث انتهت حلقة while. أعد ضبط الحالة وقم بمحاكاة إخراج عنصر من المكدس عن طريق زيادة المؤشر. c [ i ] := 0 i += 1 end if end while

في هذا البرهان، سنستخدم التنفيذ الموضح أدناه لخوارزمية الكومة، لأنه يُسهّل التحليل، ويُمكن من خلاله توضيح بعض الأنماط بسهولة. مع أنه ليس الأمثل (فهو لا يُقلّل عدد الحركات، كما هو موضح في القسم التالي)، إلا أن التنفيذ صحيح وسيُنتج جميع التباديل.

// إخراج k! من التباديل للمصفوفة A حيث يتم تبديل العناصر k الأولى بجميع الطرق. // للحصول على جميع تباديل A، استخدم k := طول A. // // إذا كان k > طول A، فسيتم محاولة الوصول إلى A خارج النطاق. // إذا كان k <= 0، فلن يكون هناك أي إخراج (المصفوفة الفارغة ليس لها تباديل) procedure permutations ( k : عدد صحيح , A : مصفوفة من أي نوع ) : if k = 1 then output ( A ) else for i := 0 ; i < k ; i += 1 do permutations ( k - 1 , A ) if k is زوجي then swap ( A [ i ] , A [ k - 1 ]) else swap ( A [ 0 ] , A [ k - 1 ]) end ifنهاية الحلقة نهاية الشرط

الادعاء: إذا كان طول المصفوفة A هو n ، فإن ذلك permutations(n, A)سيؤدي إما إلى بقاء A دون تغيير، إذا كان n فرديًا، أو، إذا كان n زوجيًا، فسيتم تدوير A إلى اليمين بمقدار 1 (يتم تحريك العنصر الأخير أمام العناصر الأخرى).

الأساس: إذا كان طول المصفوفة A يساوي 1، permutations(1, A)فسيتم إخراج A والتوقف، وبالتالي لن تتغير A. وبما أن 1 عدد فردي، فهذا ما تم الادعاء به، لذا فإن الادعاء صحيح بالنسبة للمصفوفات التي طولها 1.

الاستقراء الرياضي: إذا كانت الفرضية صحيحة للمصفوفات ذات الطول l ≥ 1، فإننا نُثبت صحتها للمصفوفات ذات الطول l + 1 (بالإضافة إلى الحالة الأساسية، يُثبت هذا صحة الفرضية للمصفوفات بجميع أطوالها). ولأن الفرضية تعتمد على ما إذا كان l فرديًا أم زوجيًا، فإننا نُثبت كل حالة على حدة.

إذا كان l عددًا فرديًا، فبحسب فرضية الاستقراء، بالنسبة لمصفوفة A طولها l ، permutations(l, A)لن يتغير A. ولكي يصح هذا الادعاء بالنسبة للمصفوفات التي طولها l + 1 (وهو عدد زوجي)، نحتاج إلى إثبات أن permutations(l+1, A)تدوير A إلى اليمين بمقدار موضع واحد. permutations(l+1, A)سيؤدي القيام بذلك أولًا إلى تدوير permutations(l, A)A (مع بقاء A دون تغيير لأن l عدد فردي)، ثم في كل تكرار i من حلقة for، سيتم تبديل العناصر في الموضعين i و l (الموضع الأخير) في A. يضع التبديل الأول العنصر l (العنصر الأخير) في الموضع 0، والعنصر 0 في الموضع l . يضع التبديل التالي العنصر في الموضع l (حيث وضع التكرار السابق العنصر 0 الأصلي) في الموضع 1، والعنصر 1 في الموضع l . في التكرار الأخير، يضع التبديل العنصر l - 1 في الموضع l ، والعنصر في الموضع l (حيث وضع التكرار السابق العنصر l - 2 الأصلي) في الموضع l - 1. لتوضيح ما سبق، انظر أدناه للحالة n = 4.

1، 2، 3، 4 ... المصفوفة الأصلية 1، 2، 3، 4 ... التكرار الأول (تبديل المصفوفة الفرعية) 4، 2، 3، 1 ... التكرار الأول (تبديل العنصر الأول إلى الموضع الأخير) 4،2،3،1 ... التكرار الثاني (تبديل المصفوفة الفرعية) 4، 1، 3، 2 ... التكرار الثاني (تبديل العنصر الثاني إلى الموضع الأخير) 4، 1، 3، 2 ... التكرار الثالث (تبديل المصفوفة الفرعية) 4، 1، 2، 3 ... التكرار الثالث (تبديل العنصر الثالث إلى الموضع الأخير) 4، 1، 2، 3 ... التكرار الرابع (تبديل المصفوفة الفرعية) 4، 1، 2، 3 ... التكرار الرابع (تبديل العنصر الرابع إلى الموضع الأخير) المصفوفة المعدلة هي نسخة مُدارة من المصفوفة الأصلية 

إذا كان l زوجيًا، فبحسب فرضية الاستقراء، بالنسبة لمصفوفة A طولها l ، فإنّ permutations(l, A)`n = 5` تُدير A إلى اليمين بمقدار موضع واحد. ولكي يصحّ هذا الادعاء بالنسبة للمصفوفات التي طولها l + 1 (وهو عدد فردي)، نحتاج إلى إثبات أنّ `n = 5` permutations(l+1, A)لا تُغيّر A. permutations(l+1, A)في كل تكرار i من حلقة `for`، سنقوم أولًا permutations(l, A)بتدوير أول l عنصر من A بمقدار موضع واحد لأنّ l زوجي، ثمّ سنُبدّل العنصرين في الموضعين 0 و l (الموضع الأخير) في A. تدوير أول l عنصر ثمّ تبديل العنصرين الأول والأخير يُكافئ تدوير المصفوفة بأكملها. وبما أنّ عدد تكرارات الحلقة يساوي عدد عناصر المصفوفة، فإنّ المصفوفة بأكملها تُدوّر حتى يعود كل عنصر إلى موضعه الأصلي. لتوضيح ما سبق، انظر أدناه للحالة n = 5.

1، 2، 3، 4، 5 ... المصفوفة الأصلية 4، 1، 2، 3، 5 ... التكرار الأول (تبديل المصفوفة الفرعية، مما يؤدي إلى تدويرها) 5، 1، 2، 3، 4 ... التكرار الأول (التبديل) 3، 5، 1، 2، 4 ... التكرار الثاني (تبديل المصفوفة الفرعية، مما يؤدي إلى تدويرها) 4، 5، 1، 2، 3 ... التكرار الثاني (التبديل) 2، 4، 5، 1، 3 ... التكرار الثالث (تبديل المصفوفة الفرعية، مما يؤدي إلى تدويرها) 3، 4، 5، 1، 2 ... التكرار الثالث (التبديل) 1، 3، 4، 5، 2 ... التكرار الرابع (تبديل المصفوفة الفرعية، مما يؤدي إلى تدويرها) 2، 3، 4، 5، 1 ... التكرار الرابع (التبديل) 5،2،3،4،1 ... التكرار الخامس (تبديل المصفوفة الفرعية، مما يؤدي إلى تدويرها) 1، 2، 3، 4، 5 ... التكرار الخامس (التبديل) تكون الحالة النهائية للمصفوفة بنفس ترتيب الحالة الأصلية 

اكتمل الآن برهان الاستقراء للادعاء، مما سيؤدي إلى توضيح سبب قيام خوارزمية الكومة بإنشاء جميع تباديل المصفوفة A. ومرة ​​أخرى، سنثبت صحة خوارزمية الكومة بالاستقراء.

الأساس: تقوم خوارزمية الكومة بتبديل مصفوفة A بحجم 1 بشكل بديهي حيث أن الناتج A هو التبديل الوحيد لـ A.

الاستقراء: لنفترض أن خوارزمية هيب تُبدّل مصفوفة بحجم i . باستخدام نتائج البرهان السابق، سيكون كل عنصر من A موجودًا في "المخزن المؤقت" مرة واحدة عند تبديل أول i عنصر. ولأن تبديلات المصفوفة يُمكن إجراؤها بتغيير مصفوفة A عن طريق إزالة عنصر x منها ثم إضافة x إلى كل تبديل للمصفوفة المُعدّلة، فإنه يترتب على ذلك أن خوارزمية هيب تُبدّل مصفوفة بحجم${\displaystyle i+1}$لأن "المخزن المؤقت" في جوهره يحتوي على العنصر المحذوف، حيث يُضاف إلى تباديل المصفوفة الفرعية ذات الحجم i . ولأن كل تكرار لخوارزمية الكومة يحتوي على عنصر مختلف من A يشغل المخزن المؤقت عند تبديل المصفوفة الفرعية، فإن كل تبديل يتم إنشاؤه لأن كل عنصر من A لديه فرصة للإضافة إلى تباديل المصفوفة A بدون عنصر المخزن المؤقت.

قد يميل البعض إلى تبسيط الصيغة التكرارية المذكورة أعلاه عن طريق تقليل عدد مرات استدعاء الدوال التكرارية. على سبيل المثال، كما يلي:

إجراء التباديل ( k : عدد صحيح ، A : مصفوفة من أي نوع ) : إذا كان k = 1 ، فأخرج ( A ) ، وإلا// استدعاء متكرر مرة واحدة لكل k من أجل i := 0 ; i < k ; i += 1 do permutations ( k - 1 , A ) // اختيار التبديل يعتمد على زوجية k (زوجي أو فردي) إذا كان k زوجيًا ، // لا يوجد تغيير عندما i == k-1 swap ( A [ i ] , A [ k - 1 ]) else // XXX تبديل إضافي غير صحيح عندما i==k-1 swap ( A [ 0 ] , A [ k - 1 ]) end ifنهاية الحلقة نهاية الشرط

سينجح هذا التنفيذ في إنتاج جميع التباديل الممكنة، ولكنه لن يقلل من حركة البيانات. فمع تفكك مكدسات الاستدعاءات المتكررة ، ينتج عن ذلك عمليات تبديل إضافية في كل مستوى. نصف هذه العمليات لن تُحدث أي تغيير .${\displaystyle A[i]}$و${\displaystyle A[k-1]}$أين${\displaystyle i==k-1}$لكن عندما${\displaystyle k}$وهذا أمر غريب، إذ ينتج عنه عمليات تبديل إضافية لـ${\displaystyle kth}$مع${\displaystyle 0th}$عنصر.

${\displaystyle n}$	${\displaystyle n!-1}$	المقايضات	إضافي = عمليات تبديل${\displaystyle -(n!-1)}$
1	0	0	0
2	1	1	0
3	5	6	1
4	23	27	4
5	119	140	21
6	719	845	126
7	5039	5922	883
8	40319	47383	7064
9	362879	426456	63577

تُغير هذه التبديلات الإضافية ترتيب${\displaystyle k-1}$العناصر البادئة.

يمكن تجنب عمليات التبديل الإضافية إما بإضافة استدعاء تكراري إضافي قبل الحلقة أو بتكرارها.${\displaystyle k-1}$مرات (كما سبق) أو التكرار${\displaystyle k}$مرات والتحقق من ذلك${\displaystyle i}$أقل من${\displaystyle k-1}$كما في:

إجراء التباديل ( k : عدد صحيح ، A : مصفوفة من أي نوع ) : إذا كان k = 1 ، فأخرج ( A ) ، وإلا// استدعاء متكرر مرة واحدة لكل k من أجل i := 0 ; i < k ; i += 1 do permutations ( k - 1 , A ) // تجنب التبديل عندما i==k-1 if ( i < k - 1 ) // يعتمد اختيار التبديل على زوجية k إذا كان k زوجيًا، فقم بالتبديل ( A [ i ] , A [ k - 1 ]) else swap ( A [ 0 ] , A [ k - 1 ]) end if end if end for end if

الخيار جمالي في المقام الأول، لكن الأخير يؤدي إلى التحقق من قيمة${\displaystyle i}$ضعف عدد المرات.

• خوارزمية ستاينهاوس-جونسون-تروتر