Project Euler — problem 24

November 20, 2012
By

(This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers)

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.

?View Code RSPLUS
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")

To leave a comment for the author, please follow the link and comment on their blog: Tony's bubble universe » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.

Sponsors

Mango solutions



RStudio homepage



Zero Inflated Models and Generalized Linear Mixed Models with R

Dommino data lab

Quantide: statistical consulting and training



http://www.eoda.de







ODSC

ODSC

CRC R books series





Six Sigma Online Training





Contact us if you wish to help support R-bloggers, and place your banner here.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)