Permutation mit Repetition Index Conversion

Question

Ich suche nach der Gleichung, um den Index einer Permutation mit Wiederholung mit bekannten Parametern zu bestimmen.

Zum Beispiel: Insgesamt $9$ Werte, $4$ A's und $5$ B's gibt insgesamt $126$ Permutationen mit Wiederholung. $$\frac{9!}{4! \cdot 5!} = 126$$

Die auf Null basierende lexikografische Reihenfolge reicht von 0 = AAAABBBBB bis 125 = BBBBBAAAA. Dieser Datensatz ist so trivial, dass ich gerade alle Werte mit Code generiert habe, aber große Datensätze sind unpraktisch. Ich weiß, dass Index 76 = BABABABAB ist, da ich eine Liste mit Antworten habe, aber ich möchte keine teilweise oder vollständige Liste erstellen.

Wie konvertiere ich eine Sequenz wie BABABABAB direkt in die Permutation mit Wiederholungsindex? Wie mache ich direkt das Gegenteil und konvertiere die Permutation mit Wiederholungsindex zurück in die Sequenz?

Ich suche nach Gleichungen / Methoden für ein nicht triviales Beispiel.

Die lexikografische Reihenfolge wird bevorzugt, ist jedoch nicht erforderlich, solange die Methode in beide Richtungen konvertieren kann (Sequenz => Index und Index => Sequenz).

Answer 1

Die Vorwärtskonvertierung wurde unter " Lexikographischer Rang einer Zeichenfolge mit doppelten Zeichen " erläutert . Kurz gesagt, ich beziehe mich auf die andere Antwort aus dieser Frage:

Wenn die $i$Das Zeichen wird wiederholt $n_i$ Mal ist dann die Gesamtzahl der Permutationen gegeben durch:

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

Wir können bei $k$th Schritt betrachten die $k$th Zeichen der angegebenen Zeichenfolge und korrigieren Sie alle Zeichen davor. Wenn Sie dieses Zeichen durch eines der vorhergehenden Zeichen ersetzen, steht jede der möglichen Permutationen vor der angegebenen Permutation.

Wir können die Anzahl solcher Permutationen mit der gegebenen Formel berechnen. Wenn Sie diese Berechnungen über alle Schritte summieren, erhalten Sie die Gesamtzahl der vorhergehenden Permutationen für die angegebene Permutation. Dies ist die Anzahl, nach der wir suchen.

Ich habe dies in Python implementiert und an Ihrem Beispiel getestet: ( Proof of 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"))

Dies gibt das erwartete Ergebnis zurück:

76

und sollte in laufen $O(m\cdot n)$ wo $m$ ist die Anzahl der eindeutigen Zeichen unter den $n$ Zeichen.

Die Rückwärtskonvertierung verwendet dieselbe Idee. Dieses Mal korrigieren wir Zeichen vom kleinsten zum größten und zählen die möglichen Permutationen, bis die Anzahl unseren Index überschreitet, bis wir jedes Zeichen fixieren (finden).

Dies wurde zusätzlich erklärt und umgesetzt in:

• " Finde die n-te lexikographische Permutation eines Strings | Set 2 " von geeksforgeeks.org.

• Algorithmus zum Finden der Multiset-Permutation bei gegebenem lexikografischen Index in StackOverflow.