inverse Permutation Index

Question

J'ai écrit une fonction qui calcule les permutations d'un tableau [a, b, c, ...] à partir d'un index, par exemple:

0 -> a b c 
1 -> a c b 
2 -> b a c 
3 -> b c a 
4 -> c a b 
5 -> c b a  

par cette fonction récursive:

function factorial(n) { return n <= 1 ? 1 : n*factorial(n-1); } 
function permutation(ar, n) { 
    if (ar.length == 1) return [ar[0]]; 
    var x = factorial(ar.length-1); // get first element 
    return ar.splice(Math.floor(n/x),1).concat(permutation(ar, n % x)) 
} 

maintenant, je suis à la recherche d'une fonction qui prend l'indice d'une permutation pour obtenir l'indice de la permutation inverse, à savoir

index perm reversed reversed index 
    **0** -> a b c -> c b a -> **5** 
    **1** -> a c b -> b c a -> **3** 
    **2** -> b a c -> c a b -> **4** 
    **3** -> b c a -> a c b -> **1** 
    **4** -> c a b -> b a c -> **2** 
    **5** -> c b a -> a b c -> **0** 

I peut calculer toutes les permutations, calculer leur inverse et construire son index, mais il semble qu'il devrait y avoir une façon mathématique d'obtenir l'indice de la permutation inverse sans le calculer.

Answer 1

Je ne sais pas s'il existe une méthode mathématique ou non pour y parvenir, mais vous pouvez y parvenir plus rapidement en utilisant un hashmap.

var dict = {}; 

dict['abc'] = 0; 
dict['acb'] = 1; 
dict['bac'] = 2; 
dict['bca'] = 3; 
dict['cab'] = 4; 
dict['cba'] = 5; 

Donc, une fois que vous avez cela, vous pouvez inverser une chaîne normale et obtenir la valeur de celui-ci son index en utilisant la hashmap ci-dessus formé.

Espérons que cela aide!

Answer 2

si vous jetez un oeil à vos permutations, vous trouverez qu'il est structuré comme suit: (exemple pour longueur = 3)

d'abord vos permutations sont divisés en 3 groupes contenant chacun 2! éléments ces sous-groupes sont ensuite divisés en 2 groupes de longueur 1! , après quoi les sous-sous-groupes ne sont plus divisés.

donc en fait votre permutation peut être « levé les yeux » en premier indiquant quel sous-groupe, il est en indiquant quel groupe puis sous-sous ... il est en

par exemple permutation 2: « bac » est dans le sous-groupe 1 (à partir de 0) et dans le sous-sous-groupe 0.

donc nous pourrions dire 2 = (1,0), comme dans 3 = 1 * (2!) + 0 * (1 !) 4 serait alors (2,0) maintenant si on retourne 2 donc c'est (0,1) et on ajoute 4, (2,0) à cela on obtiendrait (2,1) et ceci est vrai pour toutes les permutations

dans ess : (n = longueur des permutations)

écrivez votre index en tant que * (n-1)! + b * (n-2)! + ... + z * (1!) (a = étage (index/(n-1)), b = étage ((indice% (n-1))/(n-2)!), ...)

trouver un numéro de sorte que si vous retournez le plus petit et les ajouter ensemble, vous obtenez (n-1, n-2, n-3, ..., 1)

il y a probablement un effecient algoritm qui fait cela.