[Ruby] Find a permutation consisting of 0 to 9 at high speed.

Try to solve Project Euler Problem24

Problem here

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 want to speed up the answering speed of this question!

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.

1. First prepare the variable in the 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.

2. The first loop of the while statement in the 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]

3. The while statement in the perm_count function after the second loop

Repeat 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!

Acceleration result

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!

reference

High School Mathematics A [Nth character in permutation] Whiteboard [Standard] What number is it in lexicographic order? Everyone of Tsumuji

Recommended Posts

[Ruby] Find a permutation consisting of 0 to 9 at high speed.
[Ruby] How to find the sum of each digit
[Ruby] How to retrieve the contents of a double hash
A solution to the problem of blank spaces at the beginning of textarea
I tried to make a parent class of a value object in Ruby
How to find out the Java version of a compiled class file
Iterative processing of Ruby using each method (find the sum from 1 to 10)
How to change the value of a variable at a breakpoint in intelliJ
Make a note of Ruby keyword arguments
Extract a part of a string with Ruby
Ability to display a list of products
Find the difference from a multiple of 10
[Ruby On Rails] How to retrieve and display column information of multiple records linked to a specific id at once