Project Euler 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Problem 24 of Project Euler is about permutations, which is in the field of combinatorics. The posed question is as follows

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?

There is a clever way to solve it, and a brute force solution. Since the brute force algorithm still requires some thought on how to generate permutation, I will cover both methods in this post.

Brute Force

My thoughts to the brute force algorithm was to keep generating the next lexicographic permutations until I reached a million of those. However, when I set out to solve this problem, I had no clue how to actually generate them. I knew there had to be a well developed algorithm to generate permutations, so if only I could discover it.

I was rediscovering Introduction to Algorithms by TH Cormen in my search for such a permutation algorithm, when I found the clue to the second solution I will present to you. However, it did not contain a permutation algorithm. So I had to try google. I was pointed to Cut-the-knot who cited one of the algorithm bibles A Discipline of Programming by Dijkstra for the algorithm I was looking for.

I have a hard time describing what happens in the algorithm, so my recommendation to you, is to run through it on paper with a smaller example. In C# the whole brute force solution looks like

int[] perm = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

int count = 1;
int numPerm = 1000000;
while (count < numPerm) {
   int N = perm.Length;
   int i = N-1;
   while (perm[i - 1] >= perm[i]) {
        i = i - 1;
        
    }
    int j = N;
    while (perm[j - 1] <= perm[i - 1]) {
        j = j - 1;
    }
    // swap values at position i-1 and j-1
    swap(i - 1, j - 1);

    i++;
    j = N;
    while (i &lt; j) {
            swap(i - 1, j - 1);
            i++;
            j--;
        }
        count++;
    }
    
    string permNum = "";
    for (int k = 0; k &lt; perm.Length; k++) {
        permNum = permNum + perm[k];
    }

The algorithm calls a method named swap, which I have implemented as

private void swap(int i, int j) {
    int k = perm[i];
    perm[i] = perm[j];
    perm[j] = k;
}

As I said before, the algorithm is a bit hard to read, and I really encourage you to run through it with pen and paper, in order to get the feeling for it. When I run it on my computer the result is

The millionth lexicographic permutation is: 2783915460
Solution took 12 ms

So plenty fast enough for our purpose, and it scales linearly so we have plenty of margin even if we increase the number of permutations we need.

Combinatorics

The second solution I found came when I stumbled upon the fact that there are n! permutations when we have n elements to be ordered. But how can we exploit that?

First we want to figure out, which number is first in the millionth lexicographical permutation. The last nine digits can be ordered in 9! = 362880 ways. So the first 362880 permutations start with a 0. The permutations from 362881 to 725760 start with a 1 and then the permutations from 725761 to 1088640 starts with a 2. Based on that it is clear that the millionth permutation is in the third interval, and thus must start with a 2.

So the 725761st permutation is 2013456789. So now we miss 274239 permutation to reach the goal, so we can start figuring out the second number.

Since 8! = 40320, we get get that changing the number six times we reach the permutations from 241920 – 282240. So we need to take the 7th number in the list. Since the list excludes 2 we end up with 7 as the second digit of the millionth permutation. We can then continue all the way through until we got all digits.

I haven’t found a factorial function in the .NET api, so I wrote a simple one my self. I am aware that there exists efficient algorithms for it, but for this code, we only need to use small factorials. The algorithm in C# looks like

private int Factor(int i) {
    if (i &lt; 0) {
        return 0;
    }
    
    int p = 1;
    for (int j = 1; j &lt;= i; j++) {
        p *= j;
    }
    return p;
}

The rest of the algorithm looks like

int[] perm = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int N = perm.Length;
string permNum = "";
int remain = 1000000 - 1;

List numbers = new List();
for (int i = 0; i &lt; N; i++) {
    numbers.Add(i);
}

for (int i = 1; i &lt; N; i++) {
    int j = remain / Factor(N - i);
    remain = remain % Factor(N - i);
    permNum = permNum + numbers[j];
    numbers.RemoveAt(j);
    if (remain == 0) {
        break;
    }
}

for (int i = 0; i &lt; numbers.Count; i++) {
    permNum = permNum + numbers[i];
}

We break the loop once we reach zero remaining permutations. The last part of the algorithm appends the rest of the digits in case we break out of the main algorithm.

The result of running the code

The millionth lexicographic permutation is: 2783915460
Solution took 0 ms

In other words it is so fast that I can’t time it.

Closing remarks

I gave you two algorithms, one that brute forces through all permutations until we reach the right one. And an algorithm that calculates one digit at a time based on the fact that n numbers can be arranged in n! different ways.

As usual you can find the source code, if you want to execute the code.

Questions and comments are as always welcome. Have you solved it in another way?

Posted by Kristian

38 comments

I found a pretty cool way of solving this. 1000000 can be represented as 2662512110 in the Factorial number system. Then we walk through each digit in that number from right to left. We increment every digit in the output number that is greater or equal to the current digit, and then we prepend the current digit to the output number. The output number after each step:

0
10
120
2130
13240
513240
2614350
62714350
672814350
2783915460

I read about it here.

Code for the method above:

Stopwatch sw = Stopwatch.StartNew();
int n = 1000000 - 1,
    factorial = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1;

int[] factoid = new int[10];

for (int i = 9; i > 0; i--)
{
    factoid[i] = n / factorial;
    n %= factorial;
    factorial /= i;
}

for (int i = 1; i < 10; i++)
{
    for (int j = i - 1; j >= 0; j--)
    {
        if (factoid[j] >= factoid[i]) factoid[j]++;
    }
}

sw.Stop();

for (int i = 9; i >= 0; i--)
{
    Console.Write(factoid[i]);
}

Console.WriteLine();
Console.WriteLine(sw.Elapsed);
Console.ReadLine();

Just a comment:

Seems like your algorithm only works for even numbers of n-th (as in the millionth).

for instance substituting 999999 for 1000000 results in the same answer: 2783915460

Hi Fredrik

I made the last for loop the wrong way it should have been

for (int i = 0; i < numbers.Count; i++) {
    permNum = permNum + numbers[i];
}

This way it should work for 999999 as well as any other number. I have updated the original post to reflect this.

It’s a shame I haven’t learnt any C languages yet as this post would’ve been much more helpful to me.

I remember coming to this page while trying to find a clue as to how to solve this problem, this and a few other post on the net but could never quite grasp much of it. Then I read some programmers blog about his experience with permutation algorithms and it pointed out recursion. So I sat with that thought and came up with this in Python. A recursive permutation procedure that also retains lexicographic order. It’s not very efficient but simple and easy to understand I think.

def permutations(items):

    # terminal
    if len(items) == 2:
        return [''.join(items), ''.join(items[::-1])]

    # iteration
    result = []
    for i in range(len(items)):
        p_list = permutations(items[:i] + items[i + 1:])
        for p in p_list:
            result.append(items[i] + p)

    return result

I got the idea from a very simple sorting algorithm called bubble sort. If you don’t know bubble sort you either have or probably will end up coding it without even knowing it, because it’s so simple.

The terminal point of this procedure is what’s similar to bubble sort in that all it does is take two items in an array/list and swap them around, given that the number of items at that point is two; there are only two possible permutations of two items.

Walking through each part of the code:
Lets say we want an array of all permutations of 012.

which use the procedure above parsing in as the parameter our set of items as an array [0, 1, 2].

The length/number of items is not 2 but 3 so it skips the terminal point and goes on the the code beginning with # iteration.

Iterating through each item it pulls out the item. So for the first iteration [0, 1, 2] becomes [1, 2] and the procedure is called again recursively as permutations([1, 2]).

At this point there are only two items so it returns the only two possible permutations of those two items as [12, 21] and assigns it to p_list.

Upon being returned, coming back now to the previous point in the recursion tree, the item that was pulled out is now inserted at the beginning of each permutation in p_list. So 12, 21 becomes 012, 021 and those values are added/appended to the end of our final array called result.

And so on…

All we have to do is start at the first point in lexicographic order which would naturally be 0123456789 and the the order of permutations would naturally be in lexicographic order two.

Then you can just get the value at index 999999 which is the 1 millionth permutation. Note that i used integers in while walking through the code but it it’s really using strings in the actual code.

Hi Russel

Thanks for your elaborous comment. It is always fun to see other peoples solutions yours included.

I am familiar with bubble sort, for some reason sorting algorithms are always some of the first algorithms you are introduced when you learn about algorithms. I guess it is because it is easy to relate to and there are a ton of them so you can discuss complexity and so on.

Unfortunately I am not too familiar with python, especially when it comes to lists, but I think I get the gist of what it does. Nice work.

/Kristian

hey guyz the algorithm provided above is great…but difficult to understand (mysterious)….here i provide with simple algo

1.try out all possible combinations 0..9 digits(ie. 000000000-999999999)
2.consider only those valuees which are not repeated(eg.9864321057)
eliminate repeated one’s(eg123344556)


public static void main(String ar[])
{
long count=0;
A:for(int a=0;a<=9;a++)
{
for(int b=0;b<=9;b++)
{
for(int c=0;c<=9;c++)
{
for(int d=0;d<=9;d++)
{
for(int e=0;e<=9;e++)
{
for(int f=0;f<=9;f++)
{
for(int g=0;g<=9;g++)
{
for(int h=0;h<=9;h++)
{
for(int i=0;i<=9;i++)
{

for(int j=0;j<=9;j++)
{
int arr[]={a,b,c,d,e,f,g,h,i,j};
boolean cond=true;

	B:for(int m=0;m<arr.length;m++)
	{
	for(int n=m+1;n<arr.length;n++)
	{
	if(arr[n]==arr[m])
	{
	cond=false;
	break B;
	}
	else
	cond=true;
	}
	}
	if(cond)
	{

	for(int ac=0;ac<arr.length;ac++)
	System.out.print(arr[ac]);
	count++;
	System.out.println("  Count ="+count);
	if(count==1000000)
	{
	
	System.out.println("\n\n\n\nThis is the number we wannted ^^^^^" );
	break A;
	
	}
	}
	}}}}}}
	
}


}


}

}
}


any suggestions are welcum… 🙂

Hi

Wouldn’t you be able to make the same algorithm with just one iterator, and then split the number up afterwards?

hey Kristian ….thanxx for consdering my algo….

i didnt exactly get ur question….but by ‘just one iterator’ u mean to use only 1 (for loop)……

k dis can b achieved by using recurssion…..


class Lexico2
{
static final int N=10;
static int arr[]=new int[N];
static long count=0;
static boolean breakAll=false;
public static void main(String ar[])
{

forLoop(10);
}
static void forLoop(int n)
{
if(breakAll==false)
{

	int k=N-n;
		if(n==0)
		{
		boolean cond=true;

		B:for(int m=0;m<arr.length;m++)
		{
		for(int o=m+1;o<arr.length;o++)
		{
		if(arr[o]==arr[m])
		{
		cond=false;
		break B;
		}
		else
		cond=true;
		}
		}
			if(cond)
			{
			for(int a=0;a<arr.length;a++)
			System.out.print(arr[a]);
		
		
			count++;
			System.out.println();
			if(count==1000000)
			{
			System.out.println("^^^^^  This is the no. we wanted");
			breakAll=true;
			}
		
			}
	
	
		}
		else
		{
		for(int i=0;i<=(N-1);i++)
		{
		arr[k]=i;
		forLoop(n-1);
		}
		}

	}
}
}




anyways in efficiency terms this algo is worst ……

the combinotorics algo is simply gr8!! in efficiency…… 🙂

All I meant was that you should be able to just have one iterator instead of a,b,c,d… and then split the number and check instead of the other way around. I doubt it makes any difference though.

hi,
In the last paragraph it says that ” So we need to take the 7th number in the list. Since the list excludes 2 we end up with 7 as the second digit of the millionth permutation.”

shouldn’t it be like ” So we need to take the —6th—- number in the list. Since the list excludes 2 we end up with 7 as the second digit of the millionth permutation.”

oops sorry i thought it as the array index. so it should be 6 if you talk about array index, but it seems that you talk about the place not the index. Please neglect both this and previous comment.
thanks for this great tutorials. (Y)
thanks. 🙂

I see that you figured it out yourself 🙂

You don’t really have to recalculate the factorial each time. Calculate it once and then do

fact /= N - i;

at the end of the loop.

You are right it could be done like that. However, for this specific problem I didn’t see a need for it, since the performance was already good.

I was trying this in Scala and, for the brute force approach, nutted out this recursive algorithm: find the tail of the input starting from the last ascending pair, select the lowest character from the tail of this tail that is greater than the head, then sort the remainder of the tail. (If there are no ascending pairs you have finished).

It looks like this:

def nextperm(s: String) = {
  val (next, found) = s.foldRight(("".toSeq,false)){case (ch, (acc, foundPivot)) =>
    if (foundPivot) (ch +: acc, true)
    else acc match {
      case Nil => (Seq(ch), false)
      case h :: t if (ch < h) => {
        val injectChar = acc.filter(_ > ch).sorted.head
        (injectChar +: (acc.toSet + ch - injectChar).toSeq.sorted, true)
      }
      case _ => (ch +: acc, false) 
    }
  }
  if (found) Some(next.mkString) else None
}

def lexperm(s: String): Stream[String] = {
  nextperm(s).map(s2 => Stream.cons(s2, lexperm(s2))).getOrElse(Stream.empty)
}

lexperm("0123456789").drop(999998).head 
// first element of stream is second permutation, so drop 999,998

Then I discovered that permutations can be generated on SeqLike classes, so it’s actually only a one-liner and about 10 times faster. 🙂

"0123456789".permutations.drop(999999).next

Hmmm, that was just way too easy wasn’t it. But nice use of the programming language of choice.

What if repetition is allowed? how will the code change then?

I don’t think you can answer that very easily. You would need to define a little more than just “allow repetitions”. I do think the code can handle repetitions though, but I haven’t tried it.

Hi, regarding the factorial function – 0! is actually defined as 1 which would shorten your code.

From 0 to 362880 : First digit will be 0.
From 362880 to 725760 : First digit will be 1.
From 725760 to 1088640 : First digit will be 2.
As it is exceeding the millionth value, I will have 2 as my first digit.

Now for 2nd place:
From 725760 to 766080 : second digit will be 0.
From 766080 to 806400 : second digit will be 1.
From 806400 to 846720 : second digit will be 2.
From 846720 to 887040 : second digit will be 3.
From 887040 to 927360 : second digit will be 4.
From 927360 to 967680 : second digit will be 5.
From 967680 to 1008000: second digit will be 6.
Now as it is exceeding the value of millionth permutation, The second digit will be 6.?
am I wrong somewhere? I am not able to figure out how the second digit (from left) is 7 and not 6?
Can you please correct me.
Thank you so much.

During the second round, you need to exclude any number with a 2 in it, since that number is already “used”.

Hi Mike

I doubt it will give much of a speedup, but I am often proven wrong. Have you tested it?

Hi Kristian,

I just meant that it is not correct mathematically and, also, correct version is just literally shorter. I do not think that it ifluences performance 😉

Right. I was mixing 1 and 0, since 1! is handled correctly. You are right, that is a mistake which I will fix right away.

Something is wrong here with the html encoding in the code blocks 🙁

I computed permutations of string “0123456789″ using the code in http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ and I got 2785960314 as the answer. Why is that?

I am not sure that the algorithm you use do it in lexicographic order.

Hi, I managed to write the algorithm on my own. But I still couldn’t get the wright answer. And I saw you used the modulo operator to get the rest of the number for the next cycle. I put it in my code and it worked.
Could you explain why it works?

Thanks.

Best of regards

def fact(n):
if n>1:
return n*fact(n-1)
else:
return 1
num=4
num-=1
code=[]
for i in range(9):
a=num/fact(9-i)
num-=a*fact(9-i)
code.append(a)
answer=[]
list=[0,1,2,3,4,5,6,7,8,9]
for i in code:
answer.append(str(list[i]))
list.pop(i)
for i in list:
answer.append(str(i))
print “”.join(answer)

you can explain your brute force algorithm
by checking out the solution to the following problem
“Finding the next greatest number having the same digits”

1st = 0 123456789 +362 880 9!
362 880th = 0 987654321 +362 880
725 760th = 1 987654320 +40 320 8!
766 080th = 20 98765431 +40 320
806 400th = 21 98765430 +40 320
846 720th = 23 98765410 +40 320
887 040th = 24 98765310 +40 320
927 360th = 25 98764310 +40 320
967 680th = 26 98754310 +5 040 7!
972 720th = 271 9865430 +5 040
977 760th = 273 9865410 +5 040
982 800th = 274 9865310 +5 040
987 840th = 275 9864310 +5 040
992 880th = 276 9854310 +5 040
997 920th = 278 0965431 +720 6!
998 640th = 2781 965430 +720
999 360th = 2783 096541 +120 5!
999 480th = 27831 96540 +120
999 600th = 27834 96510 +120
999 720th = 27835 96410 +120
999 840th = 27836 95410 +120
999 960th = 27839 06541 +24 4!
999 984th = 278391 0654 +6 3!
999 990th = 2783914 650 +6
999 996th = 2783915 064 +2 2!
999 998th = 27839150 64 +2
1 000 000th = 27839154 60

command_codes

Thought up the combinatorics algorithm pretty much immediately within a few moments of looking at the problem (thank you high school math) – then for the life of me took forever to translate it into code.

Maybe because I too often like to code late at night when I’m tired, lel. It’s just what seems like a good idea at the time. I am a beginner dabbling. Of course we know that working memory is impaired, idea generation, executive action, etc.

After sitting down and hammering it out step by step it came easily enough. The last hurdle was the insight that what is labelled ‘remainder’ in your algorithm should begin as remainder – 1. Knew this intuitively in the back of my mind but just would not put it into code.

Need to practice whiteboarding

[…] more efficient solution is to use combinatorics, thanks to MathBlog. The last nine digits can be ordered in ways. So the first permutations start with a 0. By […]

[…] more efficient solution is to use combinatorics, thanks to MathBlog. The last nine digits can be ordered in ways. So the first permutations start with a 0. By […]

Jean-Marie Hachey

Table 1
Lexicographic Permutations
[Project Euler. Problem 24]

t (ms)
INPUT OUTPUT BruteForce; Factorial

1 0123456789; 0; 0
2 0123456798; 0; 0
3 0123456879; 0; 0
4 0123456897; 0; 0
5 0123456978; 0; 0
6 0123456987; 0; 0
7 0123457689; 0; 0
8 0123457698; 0; 0
9 0123457869; 0; 0
10 0123457896; 0; 0

1000000 2783915460; 34; 0
2000000 5468731092; 71; 0
3000000 8241697530; 105; 0
3628800 9876543210; 126; 0

First lexicographic permutation: 0123456789.
Last lexicographic permutation: 9876543210.
(10 ! = 3628800)

Sources:
1) Kristian’s algorithm
http://www.mathblog.dk/files/euler/Problem24.cs
2) Microsoft Visual C# 2010 Express

Jean-Marie Hachey

Interesting site to visit …

Permutations with repetitions
https://rosettacode.org/wiki/Permutations_with_repetitions

Jean-Marie Hachey

Problem Euler 24

A derivative …

The first lexicographic permutation of the letters in the ISO basic Latin alphabet is:
ABCDEFGHIJKLMNOPQRSTUVWXYZ

The 403291461126605635584000000th lexicographic permutation is:
ZYXWVUTSRQPONMLKJIHGFEDCBA

What is the millionth lexicographic permutation ?

Leave a Reply