Permutation identischer Elemente

Die Permutation mit Wiederholung zählt, wenn Sie von einer Gesamtzahl und den Häufigkeiten identischer Elemente ausgehen, wie viele verschiedene geordnete Anordnungen eine gemischte Sammlung annehmen kann. Halten Sie n Objekte und sind einige davon ununterscheidbare Kopien, so ist die Zahl der verschiedenen Folgen die Fakultät von n geteilt durch das Produkt der Fakultät jeder angegebenen Häufigkeit. Dieser Rechner nimmt jenes Paar entgegen — die Gesamtzahl n und die Liste der Häufigkeiten —, wertet die Identität mit exakter BigInt-Arithmetik aus und liefert die Permutationsanzahl als Dezimalzeichenkette. Es gibt keine Stichprobe, keinen Netzaufruf und keine uhrabhängige Rundung: jedes gültige Paar ergibt jedes Mal dieselbe ganze Zahl.

Was eine Permutation identischer, wiederholter Elemente zählt

Eine Permutation mit Wiederholung identischer Elemente ist die Zahl der verschiedenen geordneten Anordnungen einer endlichen Sammlung, in der sich manche Mitglieder nicht unterscheiden lassen. Schreiben Sie n für die Gesamtzahl der Positionen (oder Objekte) und n1, n2 bis nk dafür, wie oft jeder ununterscheidbare Typ vorkommt. Weil das Vertauschen zweier Kopien desselben Typs keine neue Anordnung erzeugt, überzählen die n-Fakultät Ordnungen einer vollständig beschrifteten Sammlung um n1-Fakultät für den ersten Typ, n2-Fakultät für den zweiten und so weiter.

Die exakte Identität ist daher die Fakultät von n geteilt durch das Produkt jener Fakultäten. Klassische Unterrichtskontrollen umfassen die Buchstaben von BANANA: sechs Buchstaben, drei A, zwei N und ein B, was sechs Fakultät über drei Fakultät mal zwei Fakultät mal eins Fakultät ergibt, gleich sechzig verschiedenen Wörtern, und MISSISSIPPI: elf Buchstaben mit den Häufigkeiten eins, vier, vier und zwei, was elf Fakultät über jene Fakultäten ergibt, gleich vierunddreißigtausendsechshundertfünfzig.

Das ist nicht das n-hoch-r-Produkt, das manche Lehrbücher ebenfalls Permutationen mit Wiederholung nennen: jene andere Zählung füllt r unabhängige Plätze aus einem Alphabet von n Symbolen und gleicht n hoch r. Hier ist die Länge bereits n, und die Eingabe ist die Häufigkeit jeder identischen Gruppe. Ist eine angegebene Häufigkeit größer als n, ist die Sammlung unmöglich und dieser Rechner lehnt die Anfrage ab, statt null oder eine vorzeichenbehaftete Erweiterung zurückzugeben.

Häufigkeiten, die sich zu weniger als n addieren, lassen übrige eindeutige Elemente übrig; jedes Übrige trägt eine Eins-Fakultät im Nenner bei und ändert die ganze Zahl nicht, sodass dieselbe Formel weiter gilt. Die Umsetzung stichprobt nie, hängt nie von der Uhr ab und rundet nie: sie wertet die Fakultät von n über das Produkt der angegebenen Fakultäten mit exakter BigInt-Arithmetik aus, damit große Anzahlen exakte ganze Zahlen bleiben und nicht die Mantisse einer Gleitkommazahl überlaufen.

Anagramme, Sitzpläne und Wettbewerbsorakel

Sprachlehrkräfte und Rätselautorinnen nutzen diese Anzahl, wenn sie fragen, wie viele verschiedene Wörter sich durch Umordnen einer gegebenen Zeichenkette bilden lassen: die Buchstaben sind die Elemente, das Histogramm jedes Buchstabens ist die Liste der Wiederholungszahlen, und die Antwort ist genau die Fakultät von n über das Produkt jener Fakultäten. Chemie- und Genetikaufgaben, die Perlen, Basen oder farbige Sitze mit ununterscheidbaren Kopien anordnen, folgen derselben ganzen Zahl.

Statistikdozierende führen sie ein, wenn sie Stichproben mit identischen Ausgängen dem n-hoch-r-Produkt gegenüberstellen, das unabhängige Plätze füllt, und Wettbewerbsprogrammierende brauchen ein exaktes Orakel, damit sie die mehrstellige Fakultätsdivision nicht in jedem Sprachgurt neu implementieren. Prüfungsgeneratoren können den Erfolgspfad mit n gleich sechs und repeats gleich drei, zwei und eins festnageln, was sechzig ergibt, und den Ablehnungspfad mit jeder Häufigkeit größer als n, der fehlschlagen muss statt null zurückzugeben.

Schwesterseiten können das n-hoch-r-Produkt geordneter Auswahlen mit Zurücklegen, den allgemeinen Multinomialkoeffizienten oder Permutationen ohne Wiederholung ansteuern; diese Landung ist eigens die Formulierung Permutation mit Wiederholung, wenn die Eingaben eine Gesamtzahl und die Wiederholungszahlen identischer Elemente sind. Koppeln Sie die Anzahl mit Ihrem eigenen Aufzählungscode, wenn Sie die konkreten verschiedenen Zeichenketten brauchen; diese Fähigkeit liefert nur die ganze Zahl.