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

Written by on 22 January 2011

Topics: Project Euler

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?

28 Comments For This Post I'd Love to Hear Yours!

  1. SuprDewd says:

    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.

  2. SuprDewd says:

    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();
    
  3. Fredrik says:

    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

  4. Kristian says:

    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.

  5. Russel says:

    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.

  6. Kristian says:

    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

  7. varun says:

    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… :)

  8. Kristian says:

    Hi

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

  9. varun says:

    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…… :)

  10. Kristian says:

    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.

  11. vnb says:

    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.”

  12. vnb says:

    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. :)

  13. Kristian says:

    I see that you figured it out yourself :)

  14. Avidan says:

    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.

  15. Kristian says:

    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.

  16. Jem says:

    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
  17. Kristian says:

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

  18. Adwait says:

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

  19. Kristian says:

    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.

  20. Mike says:

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

  21. Runjhun says:

    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.

  22. Kristian says:

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

  23. Kristian says:

    Hi Mike

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

  24. Mike says:

    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 ;)

  25. Kristian says:

    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.

  26. peter says:

    Something is wrong here with the html encoding in the code blocks :(

  27. Santosh says:

    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?

  28. Kristian says:

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

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.