Problem 24 "Wörterbuchsequenz" † Eine Folge ist eine geordnete Folge von Dingen. Zum Beispiel ist 3124 eine Folge von Zahlen 1, 2, 3, 4. Eine Wörterbuchreihenfolge ist eine Reihenfolge, in der alle Sequenzen in großen oder kleinen Zahlen oder in einem Wörterbuchausdruck angeordnet sind. Wenn die Sequenzen 0, 1 und 2 in der Wörterbuchreihenfolge angeordnet sind, Es wird 012 021 102 120 201 210. Was ist das 1-millionste bei der Anordnung der Bestellreihenfolge bestehend aus 0,1,2,3,4,5,6,7,8,9 in einem Wörterbuch?
Aus der Schlussfolgerung dieses Problems
nums = [0,1,2,3,4,5,6,7,8,9]
nums.permutation(10).to_a[999999].join
Das ist das Ende. Ruby hat eine hervorragende Methode namens "Permutation". Wenn Sie ein Array an den Empfänger und eine n-Größe an das Argument übergeben, werden alle Sequenzen aller Größen n generiert, so dass das Array Geben Sie einfach den 999999. (denken Sie an den Index des Arrays) aus der Liste an.
Ich mache mir Sorgen, dass die Ausführungsgeschwindigkeit langsam ist.
time ruby problem24.rb +
ruby problem24.rb 1.60s user 0.34s system 95% cpu 2.035 total
In diesem Artikel wurde die Beschleunigung des Problems erwähnt Ich habe jedoch auf den ersten Blick nicht verstanden, was ich mit diesem Code gemacht habe, daher erkläre ich ihn für meine eigene Überprüfung. Ich würde mich freuen, wenn Sie mich wissen lassen könnten, ob Ihr Verständnis fehlerhaft ist.
Hier ist zunächst der Code, den ich interpretiert und geschrieben habe. Es ist fast das gleiche wie der Originalartikel.
class Array
nums = [0,1,2,3,4,5,6,7,8,9]
n = 100_0000
def factorial(n)
if n == 1
return 1
elsif n == 0
return 1
end
return n * factorial(n - 1)
end
def perm_count(n)
n -= 1
arr = self
ans = []
while !arr.empty?
a = factorial(arr.size - 1)
m,n = n.divmod(a)
ans << (arr.delete_at(m))
end
return ans
end
puts nums.perm_count(n).join
end
Im Originalartikel erscheint die Beschreibung "(arr.size -1) .permutation_size", aber diese "permutation_size" scheint eine selbst erstellte Methode zu sein. Auch in meinem Fall habe ich eine faktorielle Methode erstellt und stattdessen verwendet.
Lassen Sie mich erklären.
perm_count vor--1, um das n-te als Index zu verwenden.
ans Array für den Rückgabewert vor.perm_countarr-Arrays gelöscht wurden, wird die Schleife fortgesetzt, bis der Zustand von [] erreicht ist.・ A = Fakultät (arr.size --1)
Die "Fakultätsfunktion" findet den "Faktor" des Arguments.
Was wir hier suchen, ist die Anzahl der Zahlenkombinationen, die folgen, wenn die erste Zahl festgelegt ist.
Beispiel)
[0,1,2,3]Beim Finden der Reihenfolge der vier Zahlen in
Zahlen ab 0 sind 3!Es gibt eine Straße.
Gleiches gilt für Fälle von 1 bis, 2 bis 3 und 3 bis.
M M, n = n.divmod (a)
Die Nummer am Anfang des Arrays ändert sich um "a way", sodass das Ergebnis von "n / a" anzeigt, welche Nummer im "arr array" derzeit am Anfang steht.
Beispiel)
arr = [0,1,2,3]
arr.permutation.to_a
=>
[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1],
[1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0],
[2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0],
[3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]
3 für Größe 4 des arr-Arrays! =Jeweils 6 Wege[0]Die Nummer ändert sich.
Zum Beispiel der 10 ..(10-1)/3!1 ist also mehr als 3.
Eine Gruppe von Zahlen ab 0[0],Eine Gruppe von Zahlen, die mit 1 beginnen[1]Wenn Sie daran denken, ist dies`arr Array`von[1]を指しているvonと同義と分かります。
In diesem Beispiel
arr = [0,1,2,3]Der erste Buchstabe der 10. Nummer ist also arr[1] =Es ist 1.
Wenn Sie die obige Liste überprüfen, ist der 10. sicherlich[1,2,3,0]Es scheint also richtig zu sein.
Nun ans[0]Die Nummer wurde festgelegt.
・ N = n / a Rest
Zu diesem Zeitpunkt gibt dieser Rest das n-te im Array an, das nur diejenigen sammelt, die mit derselben Nummer beginnen.
Speziell
[[1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0]]
Dies ist ein Array von Zahlen ab 1[3]Zeigt an.
Ans Ans << (arr.delete_at (m))
m enthält den Index im arr array der ersten festen Zahl.
Gleichzeitig mit der Zuweisung der festen Nummer zum "ans array" wird das "arr array" destruktiv geändert.
ans = []
arr [0,1,2,3]
⬇️
ans << arr.delete_at(1)
⬇️
ans = [1]
arr = [0,2,3]
perm_countWiederholen Sie Schritt 2. Wenn ans [0] bestätigt ist, identifizieren Sie die Anzahl von ans [1] und fahren Sie mit [2], [3] ,,, fort. Am Ende wird das "arr array" zu "[]", sodass alle Zahlen in das "ans array" verschoben wurden. Der Prozess ist zu diesem Zeitpunkt abgeschlossen.
ans[0] =Es stellte sich heraus, 1 zu sein.
[[1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0]]
ans[1] =Es stellte sich heraus, 2 zu sein.
[[1, 2, 0, 3], [1, 2, 3, 0]]
ans[2] =Es stellte sich heraus, 3 zu sein.
[1, 2, 3, 0]
Nachdem die Funktion "perm_count" abgeschlossen ist, übergeben Sie die Werte an den Empfänger und die Argumente und verbinden Sie das Array der Rückgabewerte mit der Funktion "join". !! Vielen Dank!
Auf diese Weise wurde die Verarbeitungsgeschwindigkeit erhöht, indem direkt auf die n-te Position zugegriffen wurde, ohne alle Sequenzen zu erzeugen. Das Ergebnis ist wie folgt.
Vor der Korrektur
ruby problem24.rb 1.60s user 0.34s system 95% cpu 2.035 total
Überarbeitet
ruby problem24.rb 0.12s user 0.11s system 75% cpu 0.305 total
Es ist ziemlich schnell!
High School Mathematics A [N-te Zeichen in der Reihenfolge] Whiteboard Edition [Standard] Welche Nummer ist in einem Wörterbuch angeordnet? Jeder von Tsumuji
Recommended Posts