كيف هذا "Lexographic النظام خوارزمية توليد" العمل ؟

Question

من ويكيبيديا:

المعجمية الجيل النظام

من أجل كل عدد ك ، 0 ≤ k <n!, الخوارزمية التالية يولد المقابلة المعجمية التقليب الأولية تسلسل sj, j = 1, ..., n:

function permutation(k, s) {
     var int n:= length(s); factorial:= 1;
     for j= 2 to n- 1 {             // compute (n- 1)!
         factorial:= factorial* j;
     }
     for j= 1 to n- 1 {
         tempj:= (k/ factorial) mod (n+ 1- j);
         temps:= s[j+ tempj]
         for i= j+ tempj to j+ 1 step -1 {
             s[i]:= s[i- 1];      // shift the chain right
         }
         s[j]:= temps;
         factorial:= factorial/ (n- j);
     }
     return s;
 }

ما هو المنطق وراء هذا ؟ كيف يعمل ؟

Answer 1

تخيل أن لديك عدد صحيح x وتريد معرفة الرقم المخصص في موقف المئات. (على سبيل المثال إذا كانت x = 4723 تريد الإجابة 7.) لحساب هذا، فأنت تقسم أولا بنسبة 100، وإلقاء الجزء الكسري. (في مثالنا، هذا يترك 47.) ثم ابحث عن الباقي عند تقسيم 10.

افترض الآن أنك تريد العثور على قيمة الرقم في موقف الآلاف. للعثور على أنه كنت تقسم أولا بمقدار 1000، قم بإلقاء الجزء الكسري، ثم أجد الباقي مرة أخرى عندما تقسم بنسبة 10.

في نظام الترقيم العشري العادي، يحمل كل مكان واحدا من 10 قيم. يمكنك ملاحظة أنه في تمريننا المكون من أرقامنا نقفلا أولا من خلال عدد المجموعات الممكنة للقيم في الأماكن الصحيحة التي نهتم بها (10 * 10 في المثال الأول). ثم نجد الباقي عند تقسيم عدد القيم المحتملة للمكان الذي نهتم به. بالطبع بكل تأكيد، الكل يحتوي الأماكن 10 من القيم المحتملة، لذلك نحن فقط قسم 10.

حاليا, ، تخيل نظام ترقيم حيث يحتفظ كل مكان بعدد مختلف من القيم. يمكن أن يكون لدينا حقنا في المكان قيمتين أو 0 أو 1. يمكن أن يكون للمكان التالي ثلاث قيم أو 0 أو 1 أو 2؛ وما إلى ذلك وهلم جرا. في هذا النظام، نعتبر مثل هذا:

  0
  1
 10
 11
 20
 21
100
101
110
111
120
121
200
201
210
211
220
...

هذا ما يعنيه Wrang-Wrang بواسطة "رقم أساسي".

الآن، يمكنك أن ترى كيف نحسب الرقم في مكان في هذا النظام. للعثور على اليمين - لا نحتاج إلى تقسيم أولا، ونجد الباقي Modulo 2، لأن هناك قيمتين محتملة للحصول على رقم في هذا العمود. للعثور على العمود التالي إلى اليسار، نقفز أولا حسب عدد المجموعات المحتملة للأرقام في الأعمدة على اليمين: يوجد عمود واحد فقط مع رقمين محتملين، لذلك نحن نقسم بنسبة 2. ثم نأخذ الباقي Modulo 3، لأن هناك ثلاث قيم محتملة لهذا العمود. استمرار اليسار، للعمود الثالث الذي نقسمه بحلول 6 (نظرا لأن الأعمدة الموجودة على اليمين تحتوي على 3 و 2 إمكانيات لكل منهما، ويتضاعفون لجعل 6) ثم تأخذ الباقي Modulo 4، لأن هناك 4 قيم محتملة في هذا العمود.

دعونا نلقي نظرة على الوظيفة:

function permutation(k, s) {
    var int n:= length(s); factorial:= 1;
    for j= 2 to n- 1 {             // compute (n- 1)!
        factorial:= factorial* j;
    }

factorial يبدأ باسم (N-1)!

    for j= 1 to n- 1 {

في كل مرة نحصل هنا، factorial يساوي (NJ)! هذا واضح في الدور الأول j= 1 ونحن نعلم أننا تهيئنا factorial إلى (N-1)! سنرى في وقت لاحق ذلك factorial هو في الواقع دائما (NJ)!

        tempj:= (k/ factorial) mod (n+ 1- j);

هنا نحن نقسم k بواسطة factorial (وهو ما يساوي (NJ)!) ورمي الباقي، ثم نأخذ بقايا عندما نقسم النتيجة (N + 1-J). انتظر لحظة، كل ما بدأت معه هو بداية مطلع! نحن فقط نجد قيمة "الرقم" في عمود NTH من اليسار باستخدام "نظام الأرقام الأساسي المتغير"!

هذا الشيء التالي يأخذ تسلسل العناصر بين المؤشرات j و j + tempj وتدويره بشكل صحيح - أي كل عنصر يتحرك مؤشر واحد، باستثناء آخر واحد، والذي يتحرك مرة أخرى إلى البداية. من المهم أن ندرك أن جميع الأرقام الموجودة على يمين الموقف J هي حسب الطلب. نحن نتفتح بشكل فعال أحدهم وخطر البقية على طول الاحتفاظ بها بالترتيب. أي واحد نتف على ذلك يعتمد على tempj. وبعد متي tempj هو 0، ونحن نختار أصغر (ولا تحتاج في الواقع إلى القيام بأي شيء)، متى tempj يساوي NJ، ونحن نختار الأكبر.

        temps:= s[j+ tempj]
        for i= j+ tempj to j+ 1 step -1 {
            s[i]:= s[i- 1];      // shift the chain right
        }
        s[j]:= temps;

التالي، (NJ)! مقسوما على (NJ) يعطي (NJ-1)! إذا كنت تفكر في الأمر، يجب أن ترى أن هذا يعني أنه عندما نعود إلى الجزء العلوي من الحلقة و j قد زيادة من قبل واحد، factorial سوف تساوي مرة أخرى (NJ)!

        factorial:= factorial/ (n- j);
    }
    return s;
}

أتمنى أن يساعد قليلا!

Answer 2

فكر في مجموعة متعددة الأبعاد، من جميع التباديل عن العناصر N، بأبعاد:

p[n][n-1][n-2]...[1]

يمكن أن يكون أي مجموعة متعددة الأبعاد خطية في صفيف 1D من البعد:

a[n*(n-1)*(n-2)*...*1]

انها مثل رقم قاعدة متغير؛ الذهاب في ترتيب القيمة الرقمية تعطيك ترتيب معجم على الأرقام.

الفهرس الذي تستخدمه للإشارة إلى tuple x [n] = على سبيل المثال (i[n],i[n-1]...,i[0]) يكون sum_j i[j]*(j!)

لذلك، فإن القسم / وزارة الدفاع يتعافى الموضع التالي من tuple.

قيمة مؤشر KTH في Tuple هي نتاج الأبعاد إلى حقها، والتي تحدث أن تكون K!

Answer 3

يقول يو الأولي التسلسل كما في[] = { 1,2,3,4,5,6 }من ن = 6;وش تريد أن تولد kth بيرم.مع 1 على Ist المكان u يمكن أن تولد 5!(أي(ن-1)!) التجاعيد مع باقي الأماكن.

1 ,.......  

ثم ش التبادل 1 و 2 و مرة أخرى u يمكن أن تولد مرة أخرى 5!التجاعيد.

2 ,.......

لذا فإن الفكرة هي إعطاء k, نحن بحاجة إلى العثور على مدى k.ما أعنيه هو:أقول ك 225 كم 5!لا ك لها:245/5!= 2 حتى إذا كان k = 245 في التقليب أريد أن توليد المقام الأول هو بالتأكيد 3 (أيa[2]) (bcoz بعد الذهاب 2*5!= 240 سوف التبادل 1 و 3) ، سوف يكون

3,1,2,4,5,6 (the array a[] obtained after shifting the chain)
(why we are shifting is to make the remaining array sorted for the 
  next iteration so that lexicographic order is maintained.)

هذا هو السبب في algo, u هل k/(ن-1)!في التكرار الأول.والحصول على ما تبقى k = k mod (ن-1)!.هذا هو الجديد قيمة k u الذهاب بشكل متكرر تفعل الشيء نفسه مع (ن-ي)!على الأماكن المتبقية.