التباديل الفريد بدون تكرارات معكوسة أو دائرية

Question

بعض الخلفية:أنا أكتب خوارزمية بحث عنيفة إلى حد ما لحل مشكلة أواجهها.وللقيام بذلك، أحتاج إلى توليد وتقييم جميع الاحتمالات لمعرفة أيها الأفضل.وبما أن التقييم يستغرق في الواقع بعض الوقت، فإنني أفضل إنشاء أقل قدر ممكن من الحلول التي تغطي مساحة البحث الخاصة بي بالكامل.علاوة على ذلك، كلما زاد عدد العناصر التي يمكنني القيام بذلك من أجلها، كلما كان ذلك أفضل.لأي رقم K هناك عادة K!التباديل، وتوليدها جميعًا سيكون أمرًا صعبًا بالنسبة للأرقام الأعلى من ~10.

مشكلة حقيقية:يجب أن تحتوي مساحة البحث على جميع التباديل لعنصرين (N مرات el1 وM مرات el2، حيث K=M+N)، مع هذه القيود:

1. يجب أن تكون فريدة من نوعها (أي.أريد فقط [a a b b b] مرة واحدة)
2. لست بحاجة إلى عكس أي التقليب (أي.إذا كان لدي [a a b]، فلا أحتاج أيضًا إلى [b a a])
3. أنا أعتبر التباديل دائرية، لذا [a a b] = [a b a] = [b a a]

إذا كنت سأتمكن من القيام بذلك، فسيتم تقليل عدد الاحتمالات بشكل كبير.نظرًا لأن K سيكون كبيرًا بشكل مثالي، فليس من الممكن إنشاء جميع التباديل أولاً ثم تصفيتها وفقًا لهذه المعايير.لقد قمت بالفعل بتنفيذ القيد الأول (انظر أدناه) وقام بتقليص الرقم من 2^K لوظيفة التباديل العادية (التموجات) في Matlab إلى K!/N!M!، وهو فوز كبير.القيد الثاني لن يؤدي إلا إلى خفض عدد الاحتمالات إلى النصف (في أفضل الأحوال)، لكنني أعتقد أن القيد الثالث يجب أن يكون قادرًا أيضًا على تقليل عدد الاحتمالات.

إذا كان أي شخص يعرف كيفية القيام بذلك، ويفضل أن يعرف أيضًا كيفية حساب عدد الاحتمالات التي ستكون هناك، فهذا من شأنه أن يساعدني كثيرًا!أفضّل الحصول على تفسير، لكن الكود جيد أيضًا (أستطيع قراءة اللغات المشابهة لـ C، وJava(Script)، وPython، وRuby، وLisp/Scheme).

---

للمهتمين:فيما يلي الخوارزمية للحصول على التباديل الفريد الذي أملكه حتى الآن:

function genPossibilities(n, m, e1, e2)
     if n == 0
         return array of m e2's
     else
         possibilities = genPossibilities(n-1, m, e1, e2)
         for every possibility:
             gain = number of new possibilities we'll get for this smaller possibility*
             for i in max(0,(m+n-gain))
                 if possibility(i) is not e1
                     add possiblity with e1 inserted in position i
         return new possibilities

• إذا كان لديك جميع التباديل لـ N-1 وM، فيمكنك استخدامها للعثور على التباديل لـ N وM عن طريق إدخال e1 فيها.لا يمكنك فقط الإدراج في كل مكان، لأنه بعد ذلك ستحصل على نسخ مكررة.لا أعرف سبب نجاح ذلك، لكن يمكنك حساب عدد الاحتمالات الجديدة التي ستولدها من احتمال قديم (أسمي هذا "المكسب").يبدأ هذا الرقم عند M+1 لأول تبديل قديم ويتناقص بمقدار واحد لكل تبديل قديم حتى يصبح صفرًا، وعند هذه النقطة يعود إلى M، وما إلى ذلك.(يعمل فقط إذا كان M>=N).لذا، إذا كنت تريد حساب التباديل لـ N=3 وM=3 وكان لديك 10 التباديل لـ N=2 وM=3، فإن مكاسبها ستكون [4 3 2 1 3 2 1 2 1 1].اطرح هذا المكسب من طول التقليب وستحصل على الفهرس الذي يمكنك من خلاله البدء في إدراج عناصر جديدة دون عمل نسخ مكررة.

Answer 1

ما تبحث عنه هو مجموعة فرعية من الأساور الثنائية (يتم تعريف المجموعة الفرعية بالضبط بواسطة n للحرف A وm للحرف B).طقم من الجميع تسمح الأساور باختلاف عدد الحروف A وB.

يطبع التعليمة البرمجية التالية التسلسل الذي تبحث عنه، ويفعل ذلك بترتيب معجمي وفي وقت مستهلك ثابت.يعتمد على الخوارزمية العامة في هذه الورقة بقلم سوادا - للحصول على شرح لكيفية عمله، راجع تلك الورقة.

#include <stdlib.h>
#include <stdio.h>

static int *a;
static int n;

void print_bracelet(int n, int a[])
{
    int i;

    printf("[");
    for (i = 0; i < n; i++)
        printf(" %c", 'a' + a[i]);
    printf(" ]\n");
}

int check_rev(int t, int i)
{
    int j;

    for (j = i+1; j <= (t + 1)/2; j++)
    {
        if (a[j] < a[t-j+1])
            return 0;
        if (a[j] > a[t-j+1])
            return -1;
    }

    return 1;
}

void gen_bracelets(int n_a, int n_b, int t, int p, int r, int u, int v, int rs)
{
    if (2 * (t - 1) > (n + r))
    {
        if (a[t-1] > a[n-t+2+r])
            rs = 0;
        else if (a[t-1] < a[n-t+2+r])
            rs = 1;
    }
    if (t > n)
    {
        if (!rs && (n % p) == 0)
            print_bracelet(n, a + 1);
    }
    else
    {
        int n_a2 = n_a;
        int n_b2 = n_b;

        a[t] = a[t-p];

        if (a[t] == 0)
            n_a2--;
        else
            n_b2--;

        if (a[t] == a[1])
            v++;
        else
            v = 0;

        if ((u == (t - 1)) && (a[t-1] == a[1]))
            u++;

        if ((n_a2 >= 0) && (n_b2 >= 0) && !((t == n) && (u != n) && (a[n] == a[1])))
        {
            if (u == v) {
                int rev = check_rev(t, u);

                if (rev == 0)
                    gen_bracelets(n_a2, n_b2, t + 1, p, r, u, v, rs);

                if (rev == 1)
                    gen_bracelets(n_a2, n_b2, t + 1, p, t, u, v, 0);
            }
            else
                gen_bracelets(n_a2, n_b2, t + 1, p, r, u, v, rs);
        }

        if (u == t)
            u--;

        if (a[t-p] == 0 && n_b > 0)
        {
            a[t] = 1;

            if (t == 1)
                gen_bracelets(n_a, n_b - 1, t + 1, t, 1, 1, 1, rs);
            else
                gen_bracelets(n_a, n_b - 1, t + 1, t, r, u, 0, rs);
        }
    }
}

int main(int argc, char *argv[])
{
    int n_a, n_b;

    if (argc < 3)
    {
        fprintf(stderr, "Usage: %s <a> <b>\n", argv[0]);
        return -2;
    }

    n_a = atoi(argv[1]);
    n_b = atoi(argv[2]);

    if (n_a < 0 || n_b < 0)
    {
        fprintf(stderr, "a and b must be nonnegative\n");
        return -3;
    }

    n = n_a + n_b;
    a = malloc((n + 1) * sizeof(int));

    if (!a)
    {
        fprintf(stderr, "could not allocate array\n");
        return -1;
    }

    a[0] = 0;

    gen_bracelets(n_a, n_b, 1, 1, 0, 0, 0, 0);

    free(a);
    return 0;
}

Answer 2

أعتقد أنك تريد إنشاء قلادات مجانية مكونة من 2 آري.يرى هذا السؤال للارتباط والأوراق وبعض التعليمات البرمجية.

Answer 3

أنت تبحث عن مجموعات - مستقلة عن النظام.قام Matlab بحساب ذلك بشكل صحيح باستخدام K!/N!M!وهي بالضبط الصيغة لحساب عدد المجموعات.

Answer 4

على افتراض أن لديك مصفوفة من جميع التباديل، يمكنك وضع محتويات المصفوفة في تجزئة.بعد ذلك سوف ينجح هذا (القليل من القوة الغاشمة، لكنها البداية):

for each (element in array of permutations){
  if (element exists in hash){
    remove each circular permutation of element in hash except for element itself
  }
}

Answer 5

إذا كان لديك عنصرين فقط، فستكون مساحتك أصغر بكثير:2^ك بدلاً من ك!.

جرب نهجا مثل هذا:

1. مرر جميع الأرقام من 1 إلى 2^k.
2. اكتب العدد على الصورة الثنائية.
3. ترجمة جميع 0s إلى a و 1s إلى b.الآن لديك التقليب.
4. خذ التسلسل الخاص بك وقم بإنشاء تسلسلات 2 كيلو عن طريق التباديل والانعكاس الدوري.ما عليك سوى تقييم واحد من هذه التسلسلات البالغ عددها 2 كيلو.
5. من بين التسلسلات 2k، اختر التسلسل الذي يتم ترتيبه أبجديًا أولاً.
6. تحقق من السجل الخاص بك لمعرفة ما إذا كنت قد قمت بهذا بالفعل.إذا كان الأمر كذلك، تخطي.
7. إذا كان هذا جديدًا، فقم بتقييمه وإضافته إلى سجل "تم إنجازه".(إذا سمحت المساحة، يمكنك إضافة جميع عناصر "العائلة" البالغ عددها 2 كيلو إلى سجل المهام، بحيث يمكنك نقل الخطوة (6) إلى اليمين بعد الخطوة (3).يمكنك أيضًا تخزين الرقم، بدلاً من تسلسل a's وb's، في سجل "تم التنفيذ".)

إذا كان لديك رموز j محتملة، بدلاً من رمزين فقط، فافعل نفس الشيء ولكن استخدم الأساس j بدلاً من الأساس 2.