Permutações únicas sem repetições espelhadas ou circulares

Question

Alguns antecedentes: estou escrevendo um algoritmo de pesquisa de força mais ou menos bruto para resolver um problema que tenho. Para fazer isso, preciso gerar e avaliar todas as possibilidades para descobrir qual é o melhor. Como a avaliação leva algum tempo, eu prefiro gerar o mínimo de soluções possíveis que cobrem completamente meu espaço de pesquisa. Além disso, quanto mais elementos eu puder fazer isso, melhor. Para qualquer número k, normalmente existem K! Permutações, e gerar todas elas serão difíceis para números superiores a ~ 10.

Problema real: o espaço de pesquisa deve conter todas as permutações de dois elementos (n vezes El1 e M vezes El2, onde k = m+n), com estas restrições:

1. Eles precisam ser únicos (ou seja, eu só quero [aabbb] uma vez)
2. Não preciso do inverso de nenhuma permutação (ou seja, se eu tiver [aAB], também não preciso [BAA])
3. Considero que as permutações são circulares, então [aAB] = [ABA] = [BAA

Se eu pudesse fazer isso, o número de possibilidades diminuiria drasticamente. Como K idealmente será grande, não é viável gerar primeiro todas as permutações e depois filtrá -las de acordo com esses critérios. Eu já fiz a primeira restrição (veja abaixo) e reduziu o número de 2^K para a função de permutações normais do Matlab (Perms) para K!/N! M!, O que é uma grande vitória. A segunda restrição reduzirá apenas o número de possibilidades pela metade (na melhor das hipóteses), mas acho que o terceiro também deve ser capaz de realmente reduzir o número de possibilidades.

Se alguém souber como fazer isso e, de preferência, também como calcular quantas possibilidades haverá, isso me ajudaria muito! Eu preferiria uma explicação, mas o código também é bom (eu posso ler idiomas do tipo C, Java (script), Python, Ruby, Lisp/Scheme).

---

Para os interessados: aqui está o algoritmo para obter apenas permutações únicas que eu tenho até agora:

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 você tiver todas as permutações para N-1 e M, poderá usá-las para encontrar as permutações para N e M inserindo E1 nelas. Você não pode simplesmente inserir em todos os lugares, porque então você recebe duplicatas. Não sei por que isso funciona, mas você pode calcular o número de novas possibilidades que gerará a partir de um antigo (eu chamo isso de 'ganho'). Esse número começa em M+1 para a primeira permutação antiga e diminui em um para cada permutação antiga até que se tornasse zero, momento em que remonta a M, etc. (só funciona se m> = n). Portanto, se você deseja calcular as permutações para n = 3 e M = 3 e tiver as 10 permutações para n = 2 e M = 3, seus ganhos serão [4 3 2 1 3 2 1 2 1 1]. Subtraia esse ganho da duração da permutação e você obtém o índice no qual pode começar a inserir novos elementos sem fazer duplicatas.

Answer 1

O que você procura é um subconjunto de braceletes 2-Ear (o subconjunto é definido por exatamente n do caractere A e M do caractere B). O conjunto de tudo As pulseiras permitem que o número de A e B varie.

O código a seguir imprime as seqüências que você procura e o faz em ordem lexical e em tempo amortizado constante. É baseado no algoritmo geral em Este artigo da Sawada - Para uma explicação de como funciona, veja esse artigo.

#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

Eu acho que você quer gerar colares gratuitos de 2 anos. Ver essa questão para link, papéis e algum código.

Answer 3

Você está procurando combinações - que são independentes de pedidos. O Matlab calculou isso corretamente com K!/N! M! que é precisamente a fórmula para calcular o número de combinações.

Answer 4

Supondo que você tenha uma matriz de todas as permutações, você pode colocar o conteúdo da matriz em um hash. Então isso funcionará (um pouco de força bruta, mas é um começo):

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 você tem apenas dois elementos, seu espaço é muito menor: 2^k em vez de k!.

Experimente uma abordagem como esta:

1. Execute todos os números de 1 a 2^k.
2. Escreva o número em forma binária.
3. Traduza todos os 0s para A e 1s para b. Agora você tem uma permutação.
4. Pegue sua sequência e gere sequências 2K por permutações cíclicas e reversão. Você só precisa avaliar 1 dessas seqüências 2K.
5. Entre as seqüências 2K, escolha a que classifica primeiro alfabeticamente.
6. Verifique seu log para ver se você já fez este. Nesse caso, pule.
7. Se este for novo, avalie -o e adicione ao log "feito". (Se o espaço permitir, você pode adicionar todos os 2K elementos da "família" ao log feito, para que você possa mover a etapa (6) para a etapa (3). Você também pode armazenar o número, em vez da sequência de A's e B's, no log "feito".)

Se você tem j possíveis símbolos, em vez de apenas dois, faça a mesma coisa, mas use a base j em vez de base 2.