الخوارزمية: كيفية العثور على التبادل المعجمية التالي

إذا وصفت باختصار ما هو الترتيب المعجمي ، فهذا هو الترتيب حسب الترتيب الأبجدي. على سبيل المثال يتم ترتيب تسلسل الأحرف - AAA → AAB → AAC → AAD → ……… → WWW - بالترتيب الأبجدي (أو في حالتنا المعجمية).

تخيل أن لديك تسلسلًا محدودًا من الأحرف ، على سبيل المثال ، 0 ، 1 ، 2 ، 5 ، 3 ، 3 ، 0 وتحتاج إلى العثور على جميع التباديل الممكنة لهذه الشخصيات. أكثرها بديهية ، ولكن الأصعب أيضًا ، هي الخوارزمية العودية ، عندما نختار الحرف الأول من التسلسل ، ثم نختار الثاني ، والثالث ، وما إلى ذلك ، بشكل متكرر ، حتى يتم تحديد جميع الأحرف من التسلسل. من الواضح أن تعقيد مثل هذه الخوارزمية هو O (n!).

ولكن اتضح أن أبسط خوارزمية لتوليد جميع التباديل في ترتيب المعاجم هو البدء بالأصغر وحساب التكرار التالي في المكان بشكل متكرر. دعونا نرى كيف نفعل ذلك.

تمامًا كما هو الحال عند حساب القيمة الصحيحة التالية ، يجب أن نحاول زيادة الجانب الأيمن من التسلسل وترك الجانب الأيسر دون تغيير.

كمثال ، خذ التسلسل أعلاه - (0 ، 1 ، 2 ، 5 ، 3 ، 3 ، 0). للحصول على تسلسل أعلى من التسلسل الأصلي ، يكفي إعادة ترتيب العنصرين الأول والثاني في الأماكن ، ولكن هذا ليس ضروريًا ، حيث يمكنك إعادة ترتيب العنصرين الثاني والثالث والحصول على تسلسل أقرب بترتيب تصاعدي. الأمر الذي سيقودنا إلى التبادل الأقرب التالي ، إلخ.

الخوارزمية المثلى في هذه الحالة ستكون التالية:

1. بادئ ذي بدء ، تحتاج إلى العثور على أكبر لاحقة غير متزايدة. في المثال أعلاه ، سيكون هذا - (5 ، 3 ، 3 ، 0). إذا حاولت إجراء أي تبديل في هذا التسلسل ، فلن يكون أعلى من التسلسل الأصلي.
   تجدر الإشارة إلى أنه يمكنك العثور على هذا التسلسل في وقت O (n) بالنظر إلى التسلسل من اليسار إلى اليمين.
2. العنصر التالي من اللاحقة هو النقطة المحورية. في حالتنا ، هذا هو 2. ستكون النقطة المحورية دائمًا أقل من العنصر الأول لللاحقة. هذا يعني أنه في اللاحقة سيكون هناك بالضرورة عنصر يتجاوز النقطة المحورية وإذا قمنا بتغيير النقطة المحورية إلى أصغر عنصر من اللاحقة يتجاوز عنصر دعم النقطة المحورية - فسوف نحصل على تسلسل يتجاوز العنصر الأصلي - في حالتنا سيكون - (0 ، 1 ، 3 ، 5 ، 3 ، 2 ، 0).
   على سبيل المثال ستكون نتيجة هذه العملية الحد الأدنى من البادئة الصاعدة الممكنة.
   
3. وفي الخطوة الأخيرة ، نحتاج إلى فرز اللاحقة بترتيب تصاعدي. على سبيل المثال نحصل على أصغر لاحقة ممكنة. في مثالنا ، سيكون (0 ، 2 ، 3 ، 5) وسيبدو التسلسل بأكمله مثل (0 ، 1 ، 3 ، 0 ، 2 ، 3 ، 5).
   

ستكون هذه القيمة إعادة الترتيب المعجمية التالية.



بالنسبة للتطبيق العملي للخوارزمية ، لم أكن أحتاجها طوال عملي طوال الوقت ، ولكن لمقابلة مع أوبر اعتقدوا خلاف ذلك :))

من أجل البساطة ، ستتم كتابة جميع التعليمات البرمجية في Go ، وأعتقد أنه من السهل على أي شخص ترجمتها إلى أي لغة برمجة أخرى.

شكراً جزيلاً لـ PYXRU و 646f67 لغرزتي بأنف في تحسين محتمل للخوارزمية - لحساب التبديل للتعقيد الخطي ببساطة عن طريق عمل اللاحقة العكسية.

func NextPermutationAlgorithm(w string) string { l := len(w) b := []byte(w) r := "no answer" for i:=l-1; i>0 ; i--{ if b[i-1] < b[i] { pivot := i for j := pivot; j < l; j++ { if b[j] <= b[pivot] && b[i-1] < b[j] { pivot = j } } b[i-1], b[pivot] = b[pivot], b[i-1] for j := l-1; i < j; i, j = i+1, j-1 { b[i], b[j] = b[j], b[i] } r = string(b) break } } return r }