permutations uniques sans répétitions ou circulaires en miroir

Question

Un peu d'histoire: J'écris une recherche de force plus ou moins brutale algorithme pour résoudre un problème que j'ai. Pour ce faire, je dois générer et évaluer toutes les possibilités pour savoir qui est le mieux. Depuis l'évaluation prend en fait un certain temps que je préférerais générer aussi peu que des solutions possibles qui couvrent complètement mon espace de recherche. En outre, plus les éléments que je peux faire pour le mieux. Pour tout nombre K il y a normalement K! permutations, et les générer tout sera difficile pour un plus grand nombre que ~ 10.

problème réel: L'espace de recherche doit contenir toutes les permutations de deux éléments (N fois EL1 et EL2 M fois, où K = M + N), ces restrictions:

1. ils doivent être uniques (à savoir que je ne veux que [a a b b b] une fois)
2. Je ne suis pas besoin de l'inverse d'une permutation (à savoir si je [a un b], je ne suis pas aussi besoin [b a a])
3. Je considère que les permutations à être circulaire, donc [a un b] = [a b a] = [b a a]

Si je serais capable de le faire, le nombre de possibilités serait considérablement réduite. Comme K sera idéalement grand, il est impossible de générer d'abord toutes les permutations et les filtrer en fonction de ces critères. Je l'ai déjà fait la première restriction (voir ci-dessous) et réduire le nombre de 2 ^ K pour la fonction de permutations normales de Matlab (perms) à K! / N! M !, qui est une grande victoire. La seconde restriction ne coupe que le nombre de possiblités dans la moitié (dans le meilleur des cas), mais je pense que le troisième devrait également être en mesure de réduire vraiment réduire le nombre de possibilités.

Si quelqu'un sait comment le faire, et de préférence aussi comment calculer le nombre de possibilités, il y aura, cela me aiderait beaucoup! Je préfère une explication, mais le code est aussi très bien (je peux lire langages de type C, Java (Script), Python, Ruby, Lisp / Scheme).

---

Pour l'intéressé: Voici l'algorithme pour obtenir seulement des permutations uniques que j'ai jusqu'à présent:

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 vous avez toutes les permutations pour N-1 et M, vous pouvez les utiliser pour trouver les permutations pour N et M en insérant e1 en eux. Vous ne pouvez pas simplement insérer partout mais, parce que vous obtiendrez des doublons. Je ne sais pas pourquoi cela fonctionne, mais vous pouvez calculer le nombre de nouvelles possibilités que vous allez générer à partir d'un ancien (je l'appelle ce « gain »). Ce numéro commence à M + 1 pour la première ancienne permutation et diminue d'une unité pour chaque ancienne permutation jusqu'à ce qu'il devienne zéro, à quel point il remonte à M, etc. (ne fonctionne que si M> = N). Donc, si vous voulez calculer les permutations pour N = 3 et M = 3 et vous avez les 10 permutations pour N = 2 et M = 3, leurs gains seront [4 3 2 1 3 2 1 2 1 1]. Soustraire ce gain de la longueur de la permutation et vous obtenez l'index auquel vous pouvez commencer à insérer de nouveaux éléments sans doublons.

Answer 1

Qu'est-ce que vous êtes après est un sous-ensemble de bracelets 2-aire (le sous-ensemble est défini par exactement n de caractère A et m de caractère B). L'ensemble de tous bracelets permet le nombre de A et B varier.

Le code suivant imprime les séquences que vous êtes après, et le fait dans l'ordre lexical et dans le temps après amortissement constant. Il est basé sur l'algorithme général cet article par Sawada - pour une explication de la façon dont cela fonctionne, voir ce document.

#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

Je pense que vous voulez générer des colliers libres 2-aire. Voir cette question lien, papiers, et un code.

Answer 3

Vous cherchez des combinaisons - qui sont indépendants l'ordre. Matlab calculé cela correctement avec K! / N! M! qui est précisément la formule de calcul du nombre de combinaisons.

Answer 4

En supposant que vous avez un tableau de toutes les permutations, vous pouvez mettre le contenu du tableau dans un hachage. Ensuite, cela fonctionnera (un peu de force brute, mais son démarrage):

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 vous avez seulement deux éléments, votre espace est beaucoup plus petit:. 2 ^ k plutôt que k

Essayez une approche comme celle-ci:

1. Exécuter par tous les nombres de 1 à 2 ^ k.
2. Écrivez le numéro sous forme binaire.
3. Traduire tous 0s à un et de 1 à b. Maintenant, vous avez une permutation.
4. Prenez votre séquence et générer des séquences 2k par des permutations cycliques et l'inversion. Vous avez seulement besoin d'évaluer 1 de ces séquences 2k.
5. Parmi les séquences 2k, choisir celui qui trie par ordre alphabétique première.
6. Vérifiez votre journal pour voir si vous avez déjà fait celui-ci. Si oui, passez directement.
7. Si celui-ci est nouvelle, évaluer et ajouter à la « fait » journal. (Si l'espace le permet, vous pouvez ajouter tous les éléments 2k de la « famille » dans le journal fait, de sorte que vous pouvez déplacer l'étape (6) à droite après l'étape (3). Vous pouvez également enregistrer le numéro, plutôt que la séquence d'un de et b de, dans le "fait" log.)

Si vous avez j symboles possibles, plutôt que deux, faire la même chose, mais utiliser la base j plutôt que la base 2.