Project Euler — problem 24

It’s a lovely day. I took a walk around the campus after lunch. The scene was enjoyable in one deep autumn day. Before the afternoon work, I’d like to spend a few moments on the 24th Euler Problem.

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012   021   102   120   201   210 What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

First of all, how many lexicographic permutations of the digits 0-9? Obviously, it’s 10*9*8*…*1, which is 10! = 3628800. One million is indeed within this range. So let’s find it out. (Here, I came up with a better solution to calculate each digit directly.)

Hint: There are 9! = 362880 permutations with 0 at the first digit so the first digit is not going to be 0 for the millionth. The next 362880 permutations start with 1′s. So it won’t be 1 either. And the 725761st-1088640th, in which lies in the millionth, start with 2′s. So the first digit of millionth is 2. Well, hope my solution is well understood. Here’s the code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

num.seq <- 0:9
n <- 1e6
Lexico <- function(num.seq, n) {
  len <- length(num.seq)  
  if (n > prod(1:len) | n < 1) {
    print("Error. The number required is beyond.")
  }
  else {
    nth <- numeric(len)  
    for (i in 1:(len - 1)) {
      if (n == 0) {
        nth[i] <- num.seq[length(num.seq)]
      }
      else {
        tmp <- prod(1:(len - i)) 
        div <- floor((n - 1) / tmp)
        nth[i] <- num.seq[div + 1]
      }
      n <- n %% tmp
      num.seq <- num.seq[num.seq != nth[i]]
    }
    nth[len] <- num.seq
    return(nth)
  }
} 
cat("The result is:", Lexico(num.seq, n), "\n")

Tags: playR, Project Euler, R