permutazioni unici con ripetizioni mirroring o circolari

Question

Alcuni retroscena: Sto scrivendo un algoritmo di ricerca forza più o meno bruta per risolvere un problema che ho. Per fare questo, ho bisogno di generare e valutare tutte le possibilità per scoprire quale sia la migliore. Dal momento che la valutazione prende in realtà un po 'di tempo io preferirei di generare il meno possibili soluzioni che coprono completamente il mio spazio di ricerca. Inoltre, i più elementi che possono fare questo per il meglio. Per qualsiasi numero K ci sono normalmente K! permutazioni, e li genera tutti sarà difficile per i numeri superiori a ~ 10.

problema reale: Lo spazio di ricerca dovrebbe contenere tutte le permutazioni di due elementi (N volte EL1 e EL2 m volte, dove K = M + N), con queste restrizioni:

1. devono essere unici (cioè io voglio solo [a a b b b] una volta)
2. Non ho bisogno il contrario di ogni permutazione (vale a dire se ho [a un b], non ho bisogno anche di [b a a])
3. ritengo le permutazioni di essere circolare, così [a a b] = [a b a] = [b a a]

Se sarei stato in grado di fare questo, il numero di possibilità sarebbe diminuita drasticamente. Poiché K idealmente essere grande, non è possibile generare prima tutte le permutazioni e poi filtrata li secondo questi criteri. Ho già fatto la prima restrizione (vedi sotto) e ridurre il numero da 2 ^ K per la funzione di permutazioni normali di Matlab (permanenti) a K! / N! M !, che è una grande vittoria. La seconda restrizione sarà solo ridurre il numero di possiblities a metà (nel migliore dei casi), ma penso che il terzo dovrebbe anche essere in grado di tagliare veramente basso il numero di possibilità.

Se qualcuno sa come farlo, e preferibilmente anche come calcolare quante possibilità ci saranno, che mi avrebbe aiutato un sacco! Io preferirei una spiegazione, ma il codice è anche bene (posso leggere C-come lingue, Java (Script), Python, Ruby, Lisp / Scheme).

---

Per gli interessati: Ecco l'algoritmo per ottenere permutazioni solo uniche che ho finora:

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

• Se si dispone di tutte le permutazioni di N-1 e M, allora si può usare per trovare le permutazioni di N e M inserendo e1 in loro. Non si può semplicemente inserire ovunque, però, perché poi si otterrà i duplicati. Non so perché questo funziona, ma è possibile calcolare il numero di nuove possibilità che verrà generato da un vecchio (che io chiamo questo 'guadagno'). Questo numero inizia da M + 1 per il primo vecchia permutazione e diminuisce di uno per ogni vecchia permutazione fino diventerebbe nullo, a quel punto risale a M, ecc (funziona solo se M> = N). Quindi, se si vuole calcolare le permutazioni di N = 3 e M = 3 e si ha il 10 permutazioni di N = 2 e M = 3, i loro guadagni saranno [4 3 2 1 3 2 1 2 1 1]. Sottrarre questo guadagno dalla lunghezza della permutazione e si ottiene l'indice a cui è possibile iniziare l'inserimento di nuovi elementi senza duplicati.

Answer 1

che cosa siete dopo è un sottoinsieme di bracciali 2-ari (il sottoinsieme è definito da esattamente n di carattere A e m di carattere B). L'insieme di tutti bracciali consente per il numero di A e B di variare.

Il codice seguente stampa i sequenze che sono dopo, e lo fa in ordine lessicale e in tempo ammortizzato costante. Essa si basa sulla algoritmo generale in questo lavoro da Sawada - per una spiegazione di come funziona, vedere che la carta.

#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

Penso che si desidera generare collane libere 2-ari. Vedi questa domanda per il link, documenti, e un po 'di codice.

Answer 3

Siete alla ricerca di combinazioni - che sono ordine indipendente. Matlab calcolato correttamente questo con K! / N! M! che è appunto la formula per calcolare il numero di combinazioni.

Answer 4

Supponendo di avere una serie di tutte le permutazioni, si può mettere il contenuto della matrice in un hash. Poi questo lavoro (un po 'di forza bruta, ma è un inizio):

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

Se si dispone di due soli elementi, il tuo spazio è molto più piccolo:!. 2 ^ k piuttosto che k

Prova un approccio come questo:

1. Esegui attraverso tutti i numeri da 1 a 2 ^ k.
2. Scrivi il numero in forma binaria.
3. Translate tutti 0 ad una e 1 a b. Ora avete una permutazione.
4. Prendete la vostra sequenza e generare sequenze 2k di permutazioni cicliche e di inversione. Hai solo bisogno di valutare 1 di queste sequenze 2k.
5. Tra le sequenze 2k, scegliere quello che ordina primo in ordine alfabetico.
6. Controlla il registro per vedere se hai già fatto questo. Se è così, salta.
7. Se questo è nuova, valutarlo, e aggiungere al registro "fatto". (Se lo spazio lo consente, è possibile aggiungere tutti gli elementi 2k della "famiglia" nel registro fatto, così si potrebbe muovere passo (6) a destra dopo il punto (3). Si potrebbe anche memorizzare il numero, piuttosto che la sequenza di una di e b è, nel "fatto" di log.)

Se avete j simboli possibili, piuttosto che solo due, fare la stessa cosa, ma utilizzare di base j invece di base 2.