Algorithmes rapides de correspondance permutation -> nombre -> permutation

Question

J'ai n éléments. Pour les besoins de l'exemple, disons 7 éléments, 1234567. Je sais qu'il y a 7 ! = 5040 permutations possibles de ces 7 éléments.

Je souhaite un algorithme rapide comprenant deux fonctions :

f(nombre) associe un nombre compris entre 0 et 5039 à une permutation unique, et

f'(permutation) renvoie la permutation au nombre à partir duquel elle a été générée.

Je ne me soucie pas de la correspondance entre le nombre et la permutation, à condition que chaque permutation ait son propre numéro.

Ainsi, par exemple, je pourrais avoir des fonctions où

f(0) = '1234567'
f'('1234567') = 0

L'algorithme le plus rapide qui me vient à l'esprit consiste à énumérer toutes les permutations et à créer une table de recherche dans les deux sens, de sorte qu'une fois les tables créées, f(0) serait O(1) et f('1234567') serait une recherche sur une chaîne de caractères. Cependant, cette méthode est gourmande en mémoire, en particulier lorsque n devient grand.

Quelqu'un peut-il proposer un autre algorithme qui fonctionnerait rapidement et sans l'inconvénient de la mémoire ?

Answer 1

Pour décrire une permutation de n éléments, vous voyez que pour la position à laquelle le premier élément aboutit, vous avez n possibilités. Vous pouvez donc décrire cela avec un nombre entre 0 et n-1. Pour la position de l'élément suivant, vous avez n-1 possibilités restantes, vous pouvez donc décrire ceci avec un nombre entre 0 et n-2.
Et cetera jusqu'à ce que vous ayez n nombres.

A titre d'exemple pour n = 5, considérons la permutation qui apporte abcde a caebd .

• a le premier élément, se retrouve en deuxième position, nous lui attribuons donc l'indice 1 .
• b se retrouve en quatrième position, ce qui correspondrait à l'index 3, mais c'est le troisième restant, nous lui attribuons donc 2 .
• c aboutit à la première position restante, qui est toujours 0 .
• d se retrouve à la dernière position restante, qui (sur seulement deux positions restantes) est 1 .
• e se retrouve à la seule position restante, indexée à 0 .

Nous avons donc la séquence d'index {1, 2, 0, 1, 0} .

Vous savez maintenant que, par exemple, dans un nombre binaire, "xyz" signifie z + 2y + 4x. Pour un nombre décimal,
c'est z + 10y + 100x. Chaque chiffre est multiplié par un certain poids et les résultats sont additionnés. Le schéma évident du poids est bien sûr que le poids est w = b^k, avec b la base du nombre et k l'indice du chiffre. (Je compterai toujours les chiffres en partant de la droite et en commençant à l'indice 0 pour le chiffre le plus à droite. De même, lorsque je parle du "premier" chiffre, je parle du chiffre le plus à droite).

Les raison La raison pour laquelle la pondération des chiffres suit ce schéma est que le nombre le plus élevé qui peut être représenté par les chiffres de 0 à k doit être inférieur d'exactement 1 au nombre le plus bas qui peut être représenté en utilisant uniquement le chiffre k+1. En binaire, 0111 doit être inférieur d'une unité à 1000. En décimal, 099999 doit être inférieur d'une unité à 100000.

Encodage en base variable
La règle importante est que l'espacement entre les nombres suivants soit exactement de 1. En réalisant cela, nous pouvons représenter notre séquence d'indices par un nombre à base variable . La base de chaque chiffre est le nombre de possibilités différentes pour ce chiffre. Pour la décimale, chaque chiffre a 10 possibilités. Dans notre système, le chiffre le plus à droite a 1 possibilité et le plus à gauche en a n. Mais comme le chiffre le plus à droite a 1 possibilité, le chiffre le plus à gauche a n possibilités. Mais comme le chiffre le plus à droite (le dernier de notre séquence) est toujours 0, nous le laissons de côté. Cela signifie qu'il nous reste les bases 2 à n. En général, le kème chiffre aura la base b[k] = k + 2. La valeur la plus élevée autorisée pour le chiffre k est h[k] = b[k] - 1 = k + 1.

Notre règle concernant les poids w[k] des chiffres exige que la somme de h[i] * w[i], où i va de i = 0 à i = k, soit égale à 1 * w[k+1]. En d'autres termes, w[k+1] = w[k] + h[k] * w[k] = w[k]*(h[k] + 1). Le premier poids w[0] doit toujours être égal à 1. En partant de là, nous avons les valeurs suivantes :

k    h[k] w[k]    

0    1    1  
1    2    2    
2    3    6    
3    4    24   
...  ...  ...
n-1  n    n!  

(La relation générale w[k-1] = k ! est facilement prouvée par induction).

Le nombre obtenu en convertissant notre séquence sera alors la somme de s[k] * w[k], avec k allant de 0 à n-1. Ici, s[k] est le kème élément (le plus à droite, en commençant par 0) de la séquence. Prenons par exemple notre séquence {1, 2, 0, 1, 0}, dont l'élément le plus à droite a été supprimé comme indiqué précédemment : {1, 2, 0, 1} . Notre somme est de 1 * 1 + 0 * 2 + 2 * 6 + 1 * 24 = 37 .

Notez que si nous prenons la position maximale pour chaque indice, nous aurons {4, 3, 2, 1, 0}, ce qui donne 119. Comme les poids de notre codage des nombres ont été choisis de manière à ne sauter aucun nombre, tous les nombres de 0 à 119 sont valides. Il y en a précisément 120, ce qui correspond à n ! pour n = 5 dans notre exemple, c'est-à-dire précisément au nombre de permutations différentes. Vous pouvez donc constater que nos nombres codés spécifient complètement toutes les permutations possibles.

Décodage à partir d'une base variable
Le décodage est similaire à la conversion en binaire ou en décimal. L'algorithme courant est le suivant :

int number = 42;
int base = 2;
int[] bits = new int[n];

for (int k = 0; k < bits.Length; k++)
{
    bits[k] = number % base;
    number = number / base;
}

Pour notre numéro de base variable :

int n = 5;
int number = 37;

int[] sequence = new int[n - 1];
int base = 2;

for (int k = 0; k < sequence.Length; k++)
{
    sequence[k] = number % base;
    number = number / base;

    base++; // b[k+1] = b[k] + 1
}

Cela décode correctement notre 37 en {1, 2, 0, 1} ( sequence serait {1, 0, 2, 1} dans cet exemple de code, mais peu importe ... tant que vous indexez de manière appropriée). Il suffit d'ajouter 0 à l'extrémité droite (n'oubliez pas que le dernier élément n'a toujours qu'une seule possibilité pour sa nouvelle position) pour retrouver notre séquence originale {1, 2, 0, 1, 0}.

Permutation d'une liste à l'aide d'une séquence d'index
Vous pouvez utiliser l'algorithme ci-dessous pour permuter une liste en fonction d'une séquence d'index spécifique. Il s'agit malheureusement d'un algorithme O(n²).

int n = 5;
int[] sequence = new int[] { 1, 2, 0, 1, 0 };
char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];
bool[] set = new bool[n];

for (int i = 0; i < n; i++)
{
    int s = sequence[i];
    int remainingPosition = 0;
    int index;

    // Find the s'th position in the permuted list that has not been set yet.
    for (index = 0; index < n; index++)
    {
        if (!set[index])
        {
            if (remainingPosition == s)
                break;

            remainingPosition++;
        }
    }

    permuted[index] = list[i];
    set[index] = true;
}

Représentation commune des permutations
Normalement, une permutation ne devrait pas être représentée de manière aussi peu intuitive que nous l'avons fait, mais simplement par la position absolue de chaque élément après l'application de la permutation. Notre exemple {1, 2, 0, 1, 0} pour abcde a caebd est normalement représentée par {1, 3, 0, 4, 2}. Chaque indice de 0 à 4 (ou en général, de 0 à n-1) apparaît exactement une fois dans cette représentation.

Il est facile d'appliquer une permutation sous cette forme :

int[] permutation = new int[] { 1, 3, 0, 4, 2 };

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

for (int i = 0; i < n; i++)
{
    permuted[permutation[i]] = list[i];
}

L'inversion est très similaire :

for (int i = 0; i < n; i++)
{
    list[i] = permuted[permutation[i]];
}

Passage de notre représentation à la représentation commune
Notez que si nous prenons notre algorithme pour permuter une liste en utilisant notre séquence d'index, et que nous l'appliquons à la permutation d'identité {0, 1, 2, ..., n-1}, nous obtenons l'algorithme suivant inverse permutation, représentée sous la forme commune. ( {2, 0, 4, 1, 3} dans notre exemple).

Pour obtenir la prémutation non inversée, nous appliquons l'algorithme de permutation que je viens de montrer :

int[] identity = new int[] { 0, 1, 2, 3, 4 };
int[] inverted = { 2, 0, 4, 1, 3 };
int[] normal = new int[n];

for (int i = 0; i < n; i++)
{
    normal[identity[i]] = list[i];
}

Vous pouvez également appliquer la permutation directement, en utilisant l'algorithme de permutation inverse :

char[] list = new char[] { 'a', 'b', 'c', 'd', 'e' };
char[] permuted = new char[n];

int[] inverted = { 2, 0, 4, 1, 3 };

for (int i = 0; i < n; i++)
{
    permuted[i] = list[inverted[i]];
}

Notez que tous les algorithmes permettant de traiter les permutations sous la forme commune sont O(n), alors que l'application d'une permutation sous notre forme est O(n²). Si vous devez appliquer une permutation plusieurs fois, convertissez-la d'abord en représentation commune.

Answer 2

J'ai trouvé un algorithme qui fonctionne en O(n) (sous les hypothèses de complexité habituelles). http://antoinecomeau.blogspot.ca/2014/07/mapping-between-permutations-and.html .

Remarque : le temps d'exécution réel de cet algorithme est O(n^2 log^2(n)) si l'on prend en compte le temps d'exécution de l'algorithme. complexité informatique de la division .

public static int[] perm(int n, int k)
{
    int i, ind, m=k;
    int[] permuted = new int[n];
    int[] elems = new int[n];

    for(i=0;i<n;i++) elems[i]=i;

    for(i=0;i<n;i++)
    {
            ind=m%(n-i);
            m=m/(n-i);
            permuted[i]=elems[ind];
            elems[ind]=elems[n-i-1];
    }

    return permuted;
}

public static int inv(int[] perm)
{
    int i, k=0, m=1;
    int n=perm.length;
    int[] pos = new int[n];
    int[] elems = new int[n];

    for(i=0;i<n;i++) {pos[i]=i; elems[i]=i;}

    for(i=0;i<n-1;i++)
    {
            k+=m*pos[perm[i]];
            m=m*(n-i);
            pos[elems[n-i-1]]=pos[perm[i]];
            elems[pos[perm[i]]]=elems[n-i-1];
    }

    return k;
}

Answer 3

La complexité peut être ramenée à n*log(n), voir section 10.1.1 ("Le code de Lehmer (table d'inversion)", http://www.jjj.de/fxt/#fxtbook passer à la section 10.1.1.1 ("Computation with large arrays" p.235) pour la méthode rapide. Le code (GPLed, C++) se trouve sur la même page web.

Answer 4

Il s'agit d'une fonction intégrée dans J :

   A. 1 2 3 4 5 6 7
0
   0 A. 1 2 3 4 5 6 7
1 2 3 4 5 6 7

   ?!7
5011
   5011 A. 1 2 3 4 5 6 7
7 6 4 5 1 3 2
   A. 7 6 4 5 1 3 2
5011

Answer 5

Chaque élément peut se trouver dans l'une des sept positions suivantes. Pour décrire la position d'un élément, il faut trois bits. Cela signifie que vous pouvez stocker la position de tous les éléments dans une valeur de 32 bits. C'est loin d'être efficace, puisque cette représentation permettrait même à tous les éléments d'être à la même position, mais je pense que le masquage des bits devrait être raisonnablement rapide.

Cependant, avec plus de 8 positions, vous aurez besoin de quelque chose de plus astucieux.