Gegeben sind zwei Zahlen a, b, so dass 1 & lt; = a, b & lt; = 10000000000 (10 ^ 10). Mein Problem ist es zu überprüfen, ob die Ziffern in ihnen Permutation voneinander sind oder nicht. Was ist der schnellste Weg? Ich dachte daran, Hashing zu verwenden, aber keine geeignete Hash-Funktion zu finden. Irgendwelche Vorschläge?
Für z.B. 123 ist eine gültige Permutation von 312
Ich möchte auch nicht die Ziffern in den Zahlen sortieren.
Wenn Sie die Zeichen der Zahlen (wie 1927 und 9721) meinen, gibt es (mindestens) ein paar Ansätze.
Wenn Sie sortieren durften, besteht eine Möglichkeit darin, einfach sprintf auf zwei Puffer zu verteilen, die Zeichen in den Puffern zu sortieren und dann festzustellen, ob die Zeichenfolgen gleich sind.
Wenn Sie jedoch die Ziffern nicht sortieren möchten, besteht eine andere Alternative darin, ein Array mit zehn Elementen einzurichten, bei dem alle Elemente zunächst auf Null gesetzt werden und dann jede Ziffer in der ersten Zahl verarbeitet wird. Inkrementieren des relevanten Elements.
Dann mache dasselbe mit der zweiten Zahl, aber dekrementiere.
Wenn es am Ende immer noch nur Nullen gibt, waren die Zahlen eine Permutation der anderen.
Dies ist insofern effizient, als es ein Algorithmus O(n) ist, wobei n die Anzahl der Ziffern in den beiden Zahlen ist. Der Pseudo-Code für solch ein Biest wäre etwa:
In C veranschaulicht das folgende vollständige Programm, wie dies getan werden kann:
%Vor%%Vor%
Übergeben Sie einfach zwei (positive) Zahlen und, vorausgesetzt, sie passen in long , wird es Ihnen sagen, ob sie die gleiche Anzahl an Ziffern haben.
a und b sind Anagramme, wenn sie die gleiche Anzahl jeder Ziffer haben. Der schnellste Weg scheint also zu sein, die Ziffern für a und b zu zählen:
%Vor%Erstellen Sie ein Array:
%Vor% In digitOccruances[X][N] speichern Sie, wie oft die Ziffer N in der Zahl X erscheint. Wenn Sie also 8675309 mit 9568733 vergleichen würden, würde das Array wie folgt aussehen:
Wenn die beiden Arrays gleich sind, sind die Zahlen Permutationen.
Dies ist ein O (n) -Algorithmus, asymptotisch gesprochen ist dies der effizienteste, den es erhalten wird (Sie können dieses Problem nicht lösen, ohne alle Ziffern mindestens einmal zu untersuchen.)
Sie können sofort false zurückgeben, wenn die Zahlen unterschiedliche Längen haben, also nehmen Sie an, dass beide von der Länge n sind. Es dauert 2n Operationen, um das Array zu füllen, und dann genau 10 Vergleiche, um das Array zu lesen. 2n + 10 ist O (n).
Ich habe diese ziemlich effiziente Lösung auf rosetacode.org gefunden. Ich hoffe, du verzeihst mir, dass ich es in Java geschrieben habe (ich fühle mich nicht wohl in C), aber die Syntax sollte mehr oder weniger die gleiche sein.
Der Code überprüft zuerst, ob die Nummern die gleiche Anzahl von Ziffern haben, und addiert dann die Ziffern nacheinander in eine Summe. Nur die Verschiebungsdistanz wird mit einem Faktor 6 multipliziert. Dies macht es unmöglich, dass kleinere Ziffern den gleichen Wert wie eine größere Ziffer bilden. Zum Beispiel würde eine '9' 64 mal '8' benötigen, um ihren Wert zu erreichen, was offensichtlich nicht möglich ist.
Dieser Code geht von einer nicht negativen Eingabe aus.
%Vor%Nun, wenn Sie eine 80GB-Tabelle erstellen können, können Sie immer tun:
%Vor%Wenn was ich richtig verstanden habe, ist eine Permutation eine Kombination der Elemente, die sich nicht wiederholen. Wenn also 123 eine gültige Permutation von 312 ist, dann auch
%Vor%und so weiter.
Auf der Grundlage dieser Annahme können Sie sagen, dass Sie zwei ganze Zahlen haben: 123456789 und 129837456. (Der Einfachheit halber nehme ich auch an, dass beide Zahlen gleich lang sind). Wenn Sie den Punkt verstanden haben, können Sie möglicherweise auch nach anderen Kombinationen und Kombinationen suchen.
Dafür müssen Sie nur die Ganzzahlen der Einheiten aus der angegebenen Zahl herausholen, z. B .:
%Vor%oder
%Vor%Ich habe dir buchstäblich einen algorithmischen Hinweis gegeben, wie man das macht, damit das leicht gemacht werden kann. Wenn Sie fertig sind, werden Sie mit separaten Ganzzahlen enden (besser diese Werte in einem Array speichern)
%Vor%Jetzt
Machen Sie dasselbe für die andere gegebene Ganzzahl, so dass Sie mit einem anderen Array von ganzen Zahlen enden werden
%Vor%Nun müssen Sie also nur noch überprüfen, ob alle Integer des zweiten Arrays im ersten Array von ganzen Zahlen vorhanden sind, wenn ja, dann sind sie eine Permutation der ganzen Zahlen des ersten Arrays oder der ersten Zahl.
Ich hoffe, das hilft.
Nicht sicher, warum Sie nicht sortieren möchten, es sei denn, das war eine Bedingung für Ihre Hausaufgabe. Für jeden, der auf diese Frage stolpert, sucht er nach dem schnellsten (und am meisten pythonischen!) Weg zu testen, ob zwei ganze Zahlen Permutationen in Python sind :
%Vor%Diese Lösung läuft in Python etwas schneller, natürlich unter Berücksichtigung der getesteten Zahlen als relativ kleine ganze Zahlen. Es funktioniert ziemlich gut für das Projekt Euler Problem 52.
Tags und Links c c++ performance