Problème 24 "Séquence de dictionnaire" † Une séquence est une séquence ordonnée de choses. Par exemple, 3124 est une séquence de nombres 1, 2, 3, 4. Un ordre de dictionnaire est un ordre dans lequel toutes les séquences sont organisées en grands ou petits nombres ou dans une expression de dictionnaire. Lorsque les séquences 0, 1 et 2 sont organisées dans l'ordre du dictionnaire, Il devient 012 021 102 120 201 210. Quel est le millionième lors de l'organisation de la séquence d'ordre constituée de 0,1,2,3,4,5,6,7,8,9 dans un dictionnaire?
De la conclusion de ce problème
nums = [0,1,2,3,4,5,6,7,8,9]
nums.permutation(10).to_a[999999].join
C'est la fin.
Ruby a une excellente méthode appelée permutation, et si vous passez un tableau au récepteur et une taille n à l'argument, il générera toutes les séquences de toutes les tailles n, de sorte que tableau Spécifiez simplement le 999999e (pensez à l'index du tableau) dans la liste.
Je crains que la vitesse d'exécution soit lente.
time ruby problem24.rb +
ruby problem24.rb 1.60s user 0.34s system 95% cpu 2.035 total
J'ai trouvé cet article mentionnant l'accélération du problème Cependant, je n'ai pas compris ce que je faisais avec ce code à première vue, donc je vais l'expliquer pour mon propre examen. Je vous serais reconnaissant si vous pouviez me faire savoir s'il y a une erreur dans votre compréhension.
Tout d'abord, voici le code que j'ai interprété et écrit. C'est presque le même que l'article original.
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
Dans l'article original, la description (arr.size -1) .permutation_size apparaît, mais cette permutation_size semble être une méthode auto-faite.
Dans mon cas également, j'ai créé une méthode «factorielle» et je l'ai utilisée à la place.
Laisse-moi expliquer.
perm_count--1 pour utiliser le nième comme index.
-Parce que le tableau créé par nums sera modifié de manière destructive après cela, préparez le tableau «arr».
-Préparez un «tableau» vide pour la valeur de retour.
perm_count-Depuis que les éléments du ʻarr tableausont supprimés, la boucle se poursuit jusqu'à ce que l'état de[]` soit atteint.
・ ʻA = factorielle (arr.size --1) Lafonction factorielle` trouve le" facteur "de l'argument.
Ce que nous recherchons ici, c'est le nombre de combinaisons de nombres qui suivent lorsque le premier nombre est fixe.
Exemple)
[0,1,2,3]Lors de la recherche de l'ordre des quatre nombres dans
Les nombres commençant par 0 sont 3!Il y a une rue.
Il en va de même pour les cas de 1 à, 2 à 3 et 3 à.
・ M, n = n.divmod (a)
Le premier nombre dans le tableau change de ʻa manière, donc le résultat de n / a montre quel nombre dans le tableau ʻarr est maintenant au début.
Exemple)
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 pour la taille 4 du tableau arr! =6 façons chacun[0]Le nombre de changera.
Par exemple, le 10(10-1)/3!Donc 1 est plus que 3.
Un groupe de nombres à partir de 0[0],Un groupe de nombres commençant par 1[1]Si vous y pensez, c'est`tableau arr`de[1]を指しているdeと同義と分かります。
Dans cet exemple
arr = [0,1,2,3]Donc, la première lettre du 10e nombre est arr[1] =C'est 1.
Certes, si vous consultez la liste ci-dessus, le 10 est[1,2,3,0]Cela semble donc correct.
Maintenant et[0]Le nombre a été décidé.
・ N = n / a reste
À ce stade, ce reste indique le nième du tableau qui ne collecte que ceux qui commencent par le même nombre.
En particulier
[[1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0]]
Ceci est un tableau de nombres commençant à 1[3]Indique.
・ ʻAns << (arr.delete_at (m)) m contient l'index dans le ʻarr tableau du premier nombre fixe.
En même temps que l'attribution du nombre fixe au ʻans tableau, le ʻarr tableau est modifié de manière destructive.
ans = []
arr [0,1,2,3]
⬇️
ans << arr.delete_at(1)
⬇️
ans = [1]
arr = [0,2,3]
perm_countRépétez l'étape 2.
Lorsque ans [0] est confirmé, identifiez le nombre de ans [1] et continuez avec [2], [3] ,,,.
A la fin, le ʻarr arraydevient[], donc tous les nombres ont été déplacés vers le ʻans array.
Le processus est terminé à ce stade.
ans[0] =S'est avéré être 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]]
ans[1] =S'est avéré être 2.
[[1, 2, 0, 3], [1, 2, 3, 0]]
ans[2] =S'est avéré être 3.
[1, 2, 3, 0]
Maintenant que la fonction perm_count est terminée, transmettez les valeurs au récepteur et les arguments, et joignez le tableau de valeurs de retour avec la fonction de jointure. !!
Merci beaucoup!
De cette manière, la vitesse de traitement a été augmentée en accédant directement à la nième position sans générer toutes les séquences. Le résultat est le suivant.
Avant correction
ruby problem24.rb 1.60s user 0.34s system 95% cpu 2.035 total
modifié
ruby problem24.rb 0.12s user 0.11s system 75% cpu 0.305 total
C'est assez rapide!
High School Mathematics A [Nth character in the order] Whiteboard Edition [Standard] Quel numéro est-il organisé dans un dictionnaire? Tout le monde de Tsumuji
Recommended Posts