permutaciones únicas sin repeticiones de espejo o circulares

Question

Algunos antecedentes: Estoy escribiendo un algoritmo más o menos fuerza bruta de búsqueda para resolver un problema que tengo. Con el fin de hacer esto, necesito generar y evaluar todas las posibilidades para saber qué es lo mejor. Dado que la evaluación de hecho lleva algún tiempo yo preferiría para generar tan poco como posibles soluciones que cubren por completo mi espacio de búsqueda. Por otra parte, los más elementos que pueden hacer esto para, mejor. Para cualquier número K no son normalmente K! permutaciones, y la generación de todos ellos será difícil para un mayor número de ~ 10.

real problema: El espacio de búsqueda debe contener todas las permutaciones de dos elementos (N veces el1 y m veces el2, donde K = M + N), con estas restricciones:

1. tienen que ser único (es decir, sólo quiero [a a b b b] una vez)
2. I no necesita la inversa de cualquier permutación (es decir, si tengo [a a b], no también necesito [b a a])
3. considero las permutaciones para ser circular, de modo [a a b] = [a b a] = [b a a]

Si yo sería capaz de hacer esto, el número de posibilidades se reduciría drásticamente. Desde K ideal será grande, no es factible generar primero todas las permutaciones y luego filtrarlos según estos criterios. Ya he hecho la primera restricción (véase más adelante) y reducir el número de 2 ^ K para la función normal de las permutaciones de Matlab (permanentes) a K! / N! M !, que es una gran victoria. La segunda restricción sólo se reducirá el número de posibilidades a la mitad (en el mejor de los casos), pero creo que el tercero también debe ser capaz de reducir realmente el número de posibilidades.

Si alguien sabe cómo hacerlo, y preferiblemente también la forma de calcular el número de posibilidades habrá, eso me ayudará mucho! Yo preferiría una explicación, pero el código también está bien (puedo leer C-idiomas, como Java (Guión), Python, Ruby, Lisp / Scheme).

---

Para los interesados: Aquí está el algoritmo para conseguir permutaciones única únicas que tengo hasta ahora:

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

• Si usted tiene todas las permutaciones de N-1 y M, entonces se puede utilizar para encontrar las permutaciones de N y M mediante la inserción E1 en ellos. No se puede simplemente insertar todas partes sin embargo, porque entonces obtendrá duplicados. No sé por qué esto funciona, pero se puede calcular el número de nuevas posibilidades que se generará a partir de un viejo (Yo llamo a esto 'ganancia'). Este número comienza a M + 1 para la primera permutación de edad y disminuye en uno por cada permutación de edad hasta que se convertiría en cero, en cuyo punto se vuelve a M, etc. (sólo funciona si M> = N). Así que si quieres para calcular las permutaciones de N = 3 y M = 3 y tiene los 10 permutaciones para N = 2 y M = 3, sus ganancias serán [4 3 2 1 3 2 1 2 1 1]. Restar este aumento de la longitud de la permutación y se obtiene el índice en el cual se puede empezar a insertar nuevos elementos sin hacer duplicados.

Answer 1

Lo que está después es un subconjunto de pulseras 2-ary (el subconjunto se define por exactamente n caracteres de A ym de carácter B). El conjunto de todos los pulseras permite el número de A y B para variar.

El siguiente código imprime las secuencias que está después, y lo hace con el fin léxico y en el tiempo amortizado constante. Se basa en el algoritmo general de este documento por Sawada - para una explicación de cómo funciona, ver que papel.

#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

Creo que desea generar collares libres 2-arias. Ver esta pregunta para el enlace, papeles y algo de código.

Answer 3

Se busca combinaciones - que son independientes del orden. Matlab calcula esto correctamente con K! / N! M! que es precisamente la fórmula para calcular el número de combinaciones.

Answer 4

Asumiendo que tiene un conjunto de todas las permutaciones, se puede poner el contenido de la matriz en un hash. Entonces esto va a trabajar (un poco de fuerza bruta, pero es un inicio):

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

Si usted tiene sólo dos elementos, su espacio es mucho menor:!. 2 ^ k en lugar de k

Trate de un enfoque como este:

1. Ejecutar a través de todos los números de 1 a 2 ^ k.
2. Escriba el número en formato binario.
3. Traducir todos los 0s y 1s a un a b. Ahora usted tiene una permutación.
4. Tome su secuencia y generar secuencias de 2k por permutaciones cíclicas y reversión. Sólo es necesario para evaluar 1 de estas secuencias 2k.
5. Entre las secuencias 2k, elegir el que ordena primero por orden alfabético.
6. Compruebe el registro para ver si ya ha hecho éste. Si es así, omita.
7. Si éste es nuevo, evaluarla, y añadir en el registro de "hecho". (Si el espacio lo permite, se puede añadir todos los elementos 2k de la "familia" en el registro de hecho, por lo que podría avanzar paso (6) a la derecha después del paso (3). También puede guardar el número, en lugar de la secuencia de una de y B, en el "hecho" de registro.)

Si usted tiene símbolos posibles j, en lugar de sólo dos, hacer lo mismo pero el uso de la base j en lugar de la base 2.