Permutation avec conversion d'index de répétition

Question

Je cherche l'équation pour déterminer l'indice d'une permutation avec répétition avec des paramètres connus.

Par exemple: un total de $9$ valeurs, $4$ A et $5$ B's Donne un total de $126$ permutations avec répétition. $$\frac{9!}{4! \cdot 5!} = 126$$

L'ordre lexicographique basé sur zéro va de 0 = AAAABBBBB à 125 = BBBBBAAAA Cet ensemble de données est suffisamment trivial pour que je viens de générer toutes les valeurs avec du code, mais de grands ensembles de données ne sont pas pratiques. Je connais cet index 76 = BABABABAB puisque j'ai une liste de réponses, mais je ne veux pas générer une liste partielle ou complète.

Comment puis-je directement convertir une séquence telle que BABABABAB en permutation avec index de répétition? Comment faire directement l'inverse et convertir la permutation avec l'index de répétition en séquence?

Je recherche les équations / méthodes à utiliser dans un exemple non trivial.

L'ordre lexicographique est préféré, mais pas obligatoire tant que la méthode peut convertir dans les deux sens (Séquence => Index et Index => Séquence).

Answer 1

La conversion vers l'avant a été expliquée dans " Rang lexicographique d'une chaîne avec des caractères en double ". En bref, je fais référence à l'autre réponse de cette question:

Si la $i$le caractère est répété $n_i$ fois, alors le nombre total de permutations est donné par:

$$ \frac{(n_1+n_2+\dots+n_m)!}{n_1!\cdot n_2! \cdot \space ... \space \cdot n_m!} $$

Nous pouvons à $k$e étape considérez le $k$ème caractère de la chaîne donnée et corrige tous les caractères avant. Maintenant, si vous remplacez ce caractère par l'un des caractères précédents, chacune des permutations possibles précédera la permutation donnée.

Nous pouvons calculer le nombre de ces permutations avec la formule donnée. La somme de ces calculs sur toutes les étapes donnera le nombre total de permutations précédentes à la permutation donnée, qui est le nombre que nous recherchons.

J'ai implémenté cela en python et l'ai testé sur votre exemple: ( preuve de concept )

from math import factorial
from functools import reduce
from collections import Counter

def lexicographical_index(string):
    [rank, l, freqs] = [0, len(string), Counter(string)]
    min_ord = min([ord(key) for key in freqs.keys()])
    for n in range(l):
        fsum = sum([freqs[chr(j)] for j in range(min_ord,ord(string[n]))])
        fprod = reduce(lambda x,y: y*x, [factorial(v) for v in freqs.values()])
        freqs[string[n]] -= 1;
        rank += ((fsum * factorial(l-n-1)) // fprod)
    return rank

print(lexicographical_index("babababab"))

qui renvoie le résultat attendu:

76

et devrait courir $O(m\cdot n)$ où $m$ est le nombre de caractères uniques parmi les $n$ chars.

La conversion vers l'arrière utilise la même idée. Cette fois-ci, nous corrigeons les caractères du plus petit au plus grand et comptons les permutations possibles jusqu'à ce que le nombre dépasse notre index, jusqu'à ce que nous corrigions (trouvions) chaque caractère.

Cela a également été expliqué et mis en œuvre dans:

• " Trouver la n-ième permutation lexicographique d'une chaîne | Set 2 " à partir de geeksforgeeks.org.

• Algorithme de recherche de permutation multisets à partir d'un index lexicographique sur StackOverflow.