In einem Programm, das ich mache, das Anagramme für einen gegebenen Satz von Buchstaben erzeugt, ist mein aktueller Ansatz:
Meine Frage bezieht sich auf die Mathematik der Permutationen. Ich frage mich, ob es möglich ist, die Array-Größe zu berechnen, die benötigt wird, um alle verbleibenden Einträge nach dem Entfernen von doppelten Einträgen zu speichern (unter Verwendung von beispielsweise der Anzahl von wiederholten Buchstaben in Verbindung mit der Permutationsformel oder etwas). p>
Ich entschuldige mich für die Unbestimmtheit meiner Frage, ich forsche immer noch mehr über Kombinationen und Permutationen. Ich werde versuchen, mein Ziel zu entwickeln, während sich mein Verständnis von Kombinationen und Permutationen erweitert, und sobald ich mich wieder mit meinem Programm vertraut mache (es war ein Freizeitprojekt von mir letzten Sommer).
Wenn Sie n elements und a[0] Duplikate eines Elements, a[1] Duplikate eines anderen Elements usw. bis a[k] haben, dann ist die Gesamtanzahl einzelner Permutationen (bis zu Duplikaten) n!/(a[0]! a[1]! ... a[k]!) .
Zu Ihrer Information, wenn Sie interessiert sind, könnten Sie Guava schreiben
%Vor% und das Ergebnis wären die einzigartigen Permutationen der Zeichen, die für Duplikate und alles verantwortlich sind. Sie könnten sogar seine .size() -Methode aufrufen - oder sehen Sie sich die Implementierung für Hinweise an. (Offenlegung: Ich trage zu Guava bei.)
Das Erzeugen aller Permutationen ist wirklich eine schlechte Idee. Das Wort "Überlauf" hat zum Beispiel 40320 Permutationen. Der Speicherverbrauch wird also mit steigender Wortlänge sehr hoch.
Ich glaube, dass das Problem, das Sie zu lösen versuchen, darauf reduziert werden kann, herauszufinden, ob ein Wort ein Anagramm eines anderen ist.
Dann können Sie es lösen, indem Sie zählen, wie oft jeder Buchstabe auftritt (es wird ein 26-Tupel sein) und diese Tupel miteinander vergleichen.
Tags und Links java math permutation combinations