Einzigartige Permutationen ohne spiegelte oder kreisförmige Wiederholungen

Question

Ein Hintergrund: Ich schreibe einen mehr oder weniger brutalen Kraft -Suchalgorithmus, um ein Problem zu lösen, das ich habe. Dazu muss ich alle Möglichkeiten generieren und bewerten, um herauszufinden, welche am besten ist. Da die Bewertung tatsächlich einige Zeit dauert, würde ich es vorziehen, so wenig wie möglich Lösungen zu generieren, die meinen Suchraum vollständig abdecken. Je mehr Elemente ich das tun kann, desto besser. Für eine beliebige Zahl k gibt es normalerweise K! Permutationen, und das Erzeugen von Zahlen über ~ 10 ist schwierig.

Echtes Problem: Der Suchraum sollte alle Permutationen von zwei Elementen (n -mal EL1- und M -mal EL2, wobei K = M+N) mit diesen Einschränkungen enthalten:

1. Sie müssen einzigartig sein (dh ich möchte nur einmal [aabbb])
2. Ich brauche nicht die Umkehrung einer Permutation (dh wenn ich [aab] habe, brauche ich auch nicht [baa])
3. Ich betrachte die Permutationen als kreisförmig, also [AAB] = [ABA] = [BAA

Wenn ich dazu in der Lage wäre, würde die Anzahl der Möglichkeiten drastisch verringert. Da K idealerweise groß ist, ist es nicht möglich, zuerst alle Permutationen zu erzeugen und dann nach diesen Kriterien zu filtern. Ich habe bereits die erste Einschränkung (siehe unten) gemacht und die Zahl von 2^k für die normale Permutationsfunktion von MATLAB auf k!/N! M!, Reduziert, was ein großer Sieg ist. Die zweite Einschränkung wird die Anzahl der Möglichkeiten nur in zwei Hälften senken (im besten Fall), aber ich denke, der dritte sollte auch in der Lage sein, die Anzahl der Möglichkeiten wirklich zu verringern.

Wenn jemand weiß, wie es geht, und vorzugsweise auch, wie viele Möglichkeiten es geben wird, würde mir das sehr helfen! Ich würde eine Erklärung bevorzugen, aber Code ist auch in Ordnung (ich kann C-ähnliche Sprachen, Java (Skript), Python, Ruby, Lisp/Schema lesen).

---

Für das Interessierte: Hier ist der Algorithmus, nur einzigartige Permutationen zu erhalten, die ich bisher habe:

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

• Wenn Sie alle Permutationen für N-1 und M haben, können Sie sie verwenden, um die Permutationen für N und M zu finden, indem Sie E1 in sie einfügen. Sie können jedoch nicht einfach überall einfügen, denn dann erhalten Sie Duplikate. Ich weiß nicht, warum dies funktioniert, aber Sie können die Anzahl der neuen Möglichkeiten berechnen, die Sie von einem alten generieren werden (ich nenne diesen "Gewinn"). Diese Zahl beginnt bei m+1 für die erste alte Permutation und nimmt für jede alte Permutation um eins ab, bis sie Null wird. An diesem Punkt geht sie zurück zu m usw. (nur dann, wenn m> = n). Wenn Sie also die Permutationen für n = 3 und m = 3 berechnen möchten und die 10 Permutationen für n = 2 und m = 3 haben, sind ihre Gewinne [4 3 2 1 3 2 1 2 1 1]. Subtrahieren Sie diesen Gewinn von der Länge der Permutation und Sie erhalten den Index, in dem Sie mit dem Einfügen neuer Elemente beginnen können, ohne Duplikate zu machen.

Answer 1

Was Sie suchen, ist eine Untergruppe von 2-Ary-Armbändern (die Teilmenge wird durch genau N von Charakter A und M von Charakter B definiert). Der Satz von alle Armbänder ermöglichen es, die Anzahl von A und B zu variieren.

Der folgende Code druckt die Sequenzen aus, nach denen Sie suchen, und dies in lexikalischer Reihenfolge und in konstant amortisierter Zeit. Es basiert auf dem allgemeinen Algorithmus in Dieses Papier von Sawada - Für eine Erklärung, wie es funktioniert, finden Sie dieses Papier.

#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

Ich denke, Sie möchten 2-Ary-freie Halsketten erzeugen. Sehen diese Frage Für Link, Papiere und etwas Code.

Answer 3

Sie suchen nach Kombinationen - die bestellen unabhängig sind. Matlab berechnete dies richtig mit k!/N! M! genau die Formel zur Berechnung der Anzahl der Kombinationen.

Answer 4

Angenommen, Sie haben eine Reihe aller Permutationen, können Sie den Inhalt des Arrays in einen Hash einfügen. Dann wird dies funktionieren (eine kleine rohe Kraft, aber es ist ein Anfang):

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

Wenn Sie nur zwei Elemente haben, ist Ihr Raum viel kleiner: 2^k anstatt K!.

Probieren Sie einen solchen Ansatz aus:

1. Führen Sie alle Zahlen von 1 bis 2^k durch.
2. Schreiben Sie die Nummer in binärer Form.
3. Übersetzen Sie alle 0s auf a und 1s auf b. Jetzt haben Sie eine Permutation.
4. Nehmen Sie Ihre Sequenz und generieren Sie 2K -Sequenzen durch zyklische Permutationen und Umkehrungen. Sie müssen nur 1 dieser 2K -Sequenzen bewerten.
5. Wählen Sie unter den 2K -Sequenzen die, die zuerst alphabetisch sortiert.
6. Überprüfen Sie Ihr Protokoll, um festzustellen, ob Sie dies bereits getan haben. Wenn ja, überspringen Sie.
7. Wenn dieser neu ist, bewerten Sie es und fügen Sie das "Done" -Protokoll hinzu. (Wenn der Platz zulässt, können Sie alle 2K -Elemente der "Familie" dem fertiggestellten Protokoll hinzufügen, sodass Sie Schritt (6) direkt nach Schritt nach Schritt (3) verschieben können. Sie können auch die Zahl speichern und nicht die Abfolge von A's und Bs, im "Fertig" -Log.)

Wenn Sie J mögliche Symbole und nicht nur zwei haben, tun Sie dasselbe, verwenden Sie aber Basis J anstelle von Base 2.