Problem 24 "Lexicographic order" † A permutation is an ordered sequence of things. For example, 3124 is a permutation of the numbers 1, 2, 3, 4. Lexicographic order is the arrangement of all permutations by number or lexicographic order. When the permutations of 0, 1 and 2 are arranged in lexicographic order. It becomes 012 021 102 120 201 210. What is the 1 millionth number when lexicographically arranging permutations consisting of 0,1,2,3,4,5,6,7,8,9?
From the conclusion of this problem
nums = [0,1,2,3,4,5,6,7,8,9]
nums.permutation(10).to_a[999999].join
This is the end.
Ruby has a super-excellent method called permutation, and if you pass an array to the receiver and an n size as an argument, it will generate all permutations of all sizes n, so that array Just specify the 999999th (think of the index of the array) from the list.
I'm worried that the execution speed is slow.
time ruby problem24.rb +
ruby problem24.rb 1.60s user 0.34s system 95% cpu 2.035 total
I found this article mentioning speeding up the issue However, at first glance I didn't understand what this code was doing, so I'll explain it for my own review. I would appreciate it if you could let me know if there is any mistake in your understanding.
First, here is the code that I interpreted and wrote. It is almost the same as the original article.
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
In the original article, the description (arr.size -1) .permutation_size appears, but this permutation_size seems to be a self-made method.
In my case as well, I created a factorial method and used it instead.
Let me explain.
perm_count function--1 to use the nth as an index.
-Since the array created by nums will be changed destructively after this, prepare the ʻarr array. -Prepare an empty ʻans array for the return value.
perm_count function-Since the elements of the ʻarr arrayare deleted, the loop is continued until the state of[]` is reached.
・ ʻA = factorial (arr.size --1) Thefactorial function` finds the" factorial "of the argument.
What we are looking for here is the number of combinations of numbers that follow when the first number is fixed.
Example)
[0,1,2,3]When finding the permutation of the four numbers in
Numbers starting from 0 are 3!There is a street.
The same applies to cases from 1 to, 2 to 3, and 3 to.
・ M, n = n.divmod (a)
The first number in the array changes by a way, so the result of n / a shows what number in the ʻarr array` is currently at the beginning.
Example)
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 for size 4 of arr array! =6 ways each[0]The number changes.
For example, the 10th(10-1)/3!So 1 is more than 3.
A group of numbers starting with 0[0],A group of numbers starting with 1[1]If you think of it, this is`arr array`of[1]を指しているofと同義と分かります。
In this example
arr = [0,1,2,3]So the first letter of the 10th number is arr[1] =It is 1.
Certainly, if you check the list above, the 10th is[1,2,3,0]So it seems to be correct.
Now ans[0]The number has been decided.
・ N = n / a remainder
At this time, this remainder indicates the nth in the array that collects only those that start with the same number.
In particular
[[1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0]]
This array of numbers starting from 1[3]Indicates.
・ ʻAns << (arr.delete_at (m)) m contains the index in the ʻarr array of the first fixed number.
At the same time as substituting the fixed numbers into the ʻans array, we are destructively changing the ʻarr array.
ans = []
arr [0,1,2,3]
⬇️
ans << arr.delete_at(1)
⬇️
ans = [1]
arr = [0,2,3]
perm_count function after the second loopRepeat step 2.
When ans [0] is confirmed, identify the number of ans [1], and continue with [2], [3] ,,,.
At the end, the ʻarr arraybecomes[], so all the numbers have moved to the ʻans array.
The process is finished at this stage.
ans[0] =Turned out to be 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] =Turned out to be 2.
[[1, 2, 0, 3], [1, 2, 3, 0]]
ans[2] =Turned out to be 3.
[1, 2, 3, 0]
Now that the perm_count function is complete, pass the values to the receiver and the arguments, and join the array of return values with the join function, and you're done! !!
Thank you very much!
In this way, the processing speed was increased by directly accessing the nth without generating all permutations. The result is as follows.
Before correction
ruby problem24.rb 1.60s user 0.34s system 95% cpu 2.035 total
Revised
ruby problem24.rb 0.12s user 0.11s system 75% cpu 0.305 total
It's pretty fast!
High School Mathematics A [Nth character in permutation] Whiteboard [Standard] What number is it in lexicographic order? Everyone of Tsumuji
Recommended Posts