Problem 024


Project Euler

Lexicographic permutations

Problem 24

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?


Another combinatorial problem where a very quick solution can be derive using permutation. Let say this problem just ask how many lexicographic permutation are there with unique digits from 0 to 9, then the solution is simply multiply each possible choice for each slots. For slot 1, there are 10 possibility. Once slot 1 is filled, there are only 9 possibility for slot 2, and so on until the last slot can only filled by the digit that didn’t get pick in the 9 previous slots to get 10! (factorial). Now, 10! is much larger than one million (3628800), therefore, the permutation could not be 9876543210 since this is 3628800th lexicographic permutation of these digits. However, 9! is 10 time smaller than 10! and so the order 0987654321 is way too low. Therefore, the first digit must be 2 because 3*9! > 1000000 but 2*9! < 1000000. Using this logic, one can calculate the lexicographic permutation of this problem by hand or by computer really quickly.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s