[C/C++] Project Euler #24 Lexicographic Permutations

The problem in Project Euler #24 is to determine the millionth lexicographic permutation of the digits 0 through 9.

 

Understanding the Method with Base Systems

How do we calculate a number in a specific base system?

For instance, to convert 723 to base 8:
We repeatedly divide the number and record the remainders. Recalling middle school mathematics, this calculation is performed as follows:

\( 723 \div 8 = 90 \, \text{remainder} \, 3 \)
\( 90 \div 8 = 11 \, \text{remainder} \, 2 \)
\( 11 \div 8 = 1 \, \text{remainder} \, 3 \)
\( 1 \div 8 = 0 \, \text{remainder} \, 1 \)

Thus,  723  in base 8 is represented as  \(1323_8 \).

In mathematical notation, this can be expressed as:

\[ 723 = 1 \cdot 8^3 + 3 \cdot 8^2 + 2 \cdot 8^1 + 3 \cdot 8^0 \]

This demonstrates that by dividing progressively by powers of the base and collecting the quotients, we arrive at the same result.

 

Applying This Concept to Permutations

How does this relate to permutations?
Permutations are similar, except for the constraint that once a digit is used, it cannot be reused.

This difference means that, unlike in base system calculations where we can compute from the least significant digit, permutations must be calculated from the most significant digit downwards.

For example, consider the digits 0, 1, 2. The permutations are:

012, 021, 102, 120, 201, 210

There are 6 permutations in total.

Similar to base systems, we use division, but instead of powers of the base, we use factorials to compute the positions.

 

Determining the Fourth Permutation

If asked for the fourth permutation, we compute using factorials:

\[ 4 = 1 \cdot 2! + 1 \cdot 1! + 0 \cdot 0! \]

This means:
• The first digit is determined by dividing by  2!, which gives a quotient of 1.  The second digit is selected accordingly.
• The remainder (1) determines the position of the second digit, using  1! .
• Finally, the last digit is determined using  0!.

Following this process:
1. The first digit (index 1) is 1.
2. The second digit (index 1 excluding the used digit) is 2.
3. The last remaining digit is 0.

Thus, the fourth permutation is 120.

 

Efficiency of the Algorithm

Using this approach, we do not need to generate all permutations to find the millionth one. Instead, we compute each digit’s position step-by-step using factorials.

 

factorial digits

 

Note: The code provided is for reference and study purposes only.

//------------------------------------------------
//    Project Euler #24 - Lexicographic Permutations
//        - by Aubrey Choi
//        - created at 2015-01-26
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

int main()
{
    int f = 3628800;
    int n = 1000000;
    int v[10];

    memset(v, 0, sizeof(v));

    n--;

    printf("Ans = ");
    for( int i = 10 ; i >= 1 ; i-- )
    {
        f /= i;
        int c = n/f;
        n = n%f;
        for( int j = 0 ; j < 10 ; j++ )
        {
            if( v[j] == 0 )
            {
                if( c == 0 ) { v[j] = 1; putchar('0'+j); break; }
                c--;
            }
        }
    }
    putchar('\n');
}