**Vikram and Neha**, and kindly contributed to R-bloggers)

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 210What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

This is a very interesting problem and it can be solved analytically. The key insight is that n distinct digits can be arranged in n! permutations.

Here’s the logic you could use. If the permutations of the numbers 0 through 9 are arranged in lexicographic order,

- The first 9! permutations, #1 to #362,880 are numbers starting with 0, in order from 0123456789 to 0987654321
- The next 9! permutations, #362,881 to #725,760, are numbers from 1023456789 to 1987654320
- The next 9! permutations, #725,761 to #1,088,640 are numbers from 2013456789 to 2987654310. The millionth permutation is contained in this set. Thus we know that the millionth number must start with a 2. In fact, it is the 274,240th = (1000000 – 725760) number contained in this set.
- Our problem has now reduced to finding the 274,240th lexicographic permutation of the numbers 0, 1, 3, 4, 5, 6, 7, 8 and 9 – the nine digits excluding 2. We can repeat the above process to get each successive digit.

1000000 = (a1 x 9!) + (a2 x 8!) + … + (a10 x 1)

findperm <- function (n) {

# Find the indices a1 - a10

indices = c()

for (i in 9:0) {

index = 0

while (factorial (i) < n) {

n = n - factorial (i)

index = index + 1

}

indices = c(indices, index)

}

# Use the indices to find the nth permutation

input = 0:9 # The list of numbers to permute

output = c()

for (j in 1:10) {

output[j] = input[indices[j] + 1] # Move digit to output

input = input[-(indices[j] + 1)] # Remove the assigned digits from input

}

return (output)

}

That was straight-forward and a fun illustration of R’s capabilities.

But you can do better. The strength of R lies in the wealth of user defined libraries and functions that can ease the implementation of tricky computation. For a simpler solution, try the lexicographicPermutation function in the library R.basic. Here is the entire solution.

The first solution illustrates that even tricky computation can be coded easily in R and the code is pretty readable. The second solution suggests that before writing your own code, it is a good idea to look for existing libraries that can help. Statistical computations can get complex and tricky. You can write your own k-means clustering algorithm but it is difficult getting all the edge cases correct. Rather than writing your own routine, look around and see if it has been written already. An expert does a better job writing such routines. And you can leverage their code and their expertise.

**leave a comment**for the author, please follow the link and comment on his blog:

**Vikram and Neha**.

R-bloggers.com offers

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