Classement et non classement des permutations avec doublons

Je lis sur les permutations et je suis intéressé par les méthodes de classement / non classé.

Extrait du résumé d’un article:

Une fonction de classement pour les permutations sur n symboles atsortingbue un entier unique dans la plage [0, n! – 1] à chacun des n! permutations. La fonction non classée correspondante est l’inverse: à partir d’un entier compris entre 0 et n! – 1, la valeur de la fonction est la permutation ayant ce rang.

J’ai créé un classement et une fonction non classée en C ++ à l’aide de next_permutation. Mais ce n’est pas pratique pour n> 8. Je cherche une méthode plus rapide et les factoradics semblent être très populaires. Mais je ne suis pas sûr que cela fonctionne aussi avec les doublons. Alors, quel serait un bon moyen de classer / réduire les permutations avec des doublons?

    L’une des méthodes consiste à classer et à annuler le choix des indices par un groupe particulier de nombres égaux,

    def choose(n, k): c = 1 for f in xrange(1, k + 1): c = (c * (n - f + 1)) // f return c def rank_choice(S): k = len(S) r = 0 j = k - 1 for n in S: for i in xrange(j, n): r += choose(i, j) j -= 1 return r def unrank_choice(k, r): S = [] for j in xrange(k - 1, -1, -1): n = j while r >= choose(n, j): r -= choose(n, j) n += 1 S.append(n) return S def rank_perm(P): P = list(P) r = 0 for n in xrange(max(P), -1, -1): S = [] for i, p in enumerate(P): if p == n: S.append(i) S.reverse() for i in S: del P[i] r *= choose(len(P) + len(S), len(S)) r += rank_choice(S) return r def unrank_perm(M, r): P = [] for n, m in enumerate(M): S = unrank_choice(m, r % choose(len(P) + m, m)) r //= choose(len(P) + m, m) S.reverse() for i in S: P.insert(i, n) return tuple(P) if __name__ == '__main__': for i in xrange(60): print rank_perm(unrank_perm([2, 3, 1], i)) 

    Pour les grands ns, vous avez besoin d’une bibliothèque de précision arbitraire comme GMP .

    Ceci est mon post précédent pour une fonction non classée écrite en python, je pense que c’est lisible, presque comme un pseudocode, il y a aussi une explication dans les commentaires: Étant donné une liste d’éléments dans l’ordre lexicographique (ie [‘a’, ‘b’ , ‘c’, ‘d’]), trouver la nième permutation – Temps moyen de résolution?

    sur cette base, vous devriez être capable de comprendre la fonction de classement, c’est fondamentalement la même logique;)

    Je vais couvrir la moitié de votre question dans cette réponse – «non classé». Le but est de trouver efficacement la permutation lexicographiquement ‘K’th d’une chaîne ordonnée [abcd …].

    Pour cela, nous devons comprendre le système de nombres factoriels (factoradics). Un système de nombres factoriels utilise des valeurs factorielles au lieu de puissances de nombres (système binary utilise des puissances de 2, décimal utilise des puissances de 10) pour désigner des valeurs de position (ou base).

    Les valeurs de position (base) sont –

     5!= 120 4!= 24 3!=6 2!= 2 1!=1 0!=1 etc.. 

    Le chiffre à la place zéro est toujours 0. Le chiffre à la première place (avec base = 1!) Peut être 0 ou 1. Le chiffre à la deuxième place (avec base 2!) Peut être 0,1 ou 2 et ainsi de suite. sur. De manière générale, le chiffre à la nième place peut prendre n’importe quelle valeur entre 0 et n.

    Quelques premiers chiffres représentés en factoradics-

     0 -> 0 = 0*0! 1 -> 10 = 1*1! + 0*0! 2 -> 100 = 1*2! + 0*1! + 0*0! 3 -> 110 = 1*2! + 1*1! + 0*0! 4 -> 200 = 2*2! + 0*1! + 0*0! 5 -> 210 = 2*2! + 1*1! + 0*0! 6 -> 1000 = 1*3! + 0*2! + 0*1! + 0*0! 7 -> 1010 = 1*3! + 0*2! + 1*1! + 0*0! 8 -> 1100 = 1*3! + 1*2! + 0*1! + 0*0! 9 -> 1110 10-> 1200 

    Il existe une relation directe entre la n-ième permutation lexicographique d’une chaîne et sa représentation factoradique.

    Par exemple, voici les permutations de la chaîne “abcd”.

     0 abcd 6 bacd 12 cabd 18 dabc 1 abdc 7 badc 13 cadb 19 dacb 2 acbd 8 bcad 14 cbad 20 dbac 3 acdb 9 bcda 15 cbda 21 dbca 4 adbc 10 bdac 16 cdab 22 dcab 5 adcb 11 bdca 17 cdba 23 dcba 

    Nous pouvons voir un motif ici, s’il est observé attentivement. La première lettre change après chaque 6 ème (3!) Permutation. La deuxième lettre change après 2 (2!) Permutation. La troisième lettre change après chaque (1!) Permutation et la quasortingème lettre change après chaque (0!) Permutation. Nous pouvons utiliser cette relation pour trouver directement la n-ième permutation.

    Une fois que nous représentons n dans une représentation factoradique, nous considérons chaque chiffre et ajoutons un caractère de la chaîne donnée à la sortie. Si nous devons trouver la 14ème permutation de ‘abcd’. 14 en factoradiques -> 2100.

    Commencez par le premier chiffre -> 2, Ssortingng est ‘abcd’. En supposant que l’index commence à 0, prenez l’élément en position 2 de la chaîne et ajoutez-le à la sortie.

     Output Ssortingng c abd 2 012 

    Le chiffre suivant -> 1.Chaine est maintenant ‘abd’. Encore une fois, cueillez le caractère en position 1 et ajoutez-le à la sortie.

     Output Ssortingng cb ad 21 01 

    Chiffre suivant -> 0. La chaîne est ‘ad’. Ajoutez le caractère en position 1 à la sortie.

     Output Ssortingng cba d 210 0 

    Chiffre suivant -> 0. La chaîne est ‘d’. Ajoutez le caractère en position 0 à la sortie.

    Chaîne de sortie cbad ” 2100

    Pour convertir un nombre donné en système de nombres factoriels, divisez le nombre par 1,2,3,4,5 et ainsi de suite jusqu’à ce que le quotient soit égal à zéro. Les rappels à chaque étape forment la représentation factoradique.

    Par exemple, convertir 349 en factoradique,

      Quotient Reminder Factorial Representation 349/1 349 0 0 349/2 174 1 10 174/3 58 0 010 58/4 14 2 2010 14/5 2 4 42010 2/6 0 2 242010 

    La représentation factorielle de 349 est 242010.

    Java, à partir de https://github.com/timtiemens/permute/blob/master/src/main/java/permute/PermuteUtil.java (mon code de domaine public moins la vérification d’erreur):

     public class PermuteUtil { public  List nthPermutation(List original, final BigInteger permutationNumber) { final int size = original.size(); // the return list: List ret = new ArrayList<>(); // local mutable copy of the original list: List numbers = new ArrayList<>(original); // Our input permutationNumber is [1,N!], but array indexes are [0,N!-1], so subtract one: BigInteger permNum = permutationNumber.subtract(BigInteger.ONE); for (int i = 1; i <= size; i++) { BigInteger factorialNminusI = factorial(size - i); // casting to integer is ok here, because even though permNum _could_ be big, // the factorialNminusI is _always_ big int j = permNum.divide(factorialNminusI).intValue(); permNum = permNum.mod(factorialNminusI); // remove item at index j, and put it in the return list at the end T item = numbers.remove(j); ret.add(item); } return ret; } }