Problem 24: Lexicographic Permutations

View on Project Euler

Project Euler Problem 24 Solution

EulerSolve provides an optimized solution for Project Euler Problem 24, Lexicographic Permutations, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The problem asks for the millionth permutation of the digits \(0,1,2,\dots,9\) when all \(10!\) permutations are listed in lexicographic order. More generally, given any ordered set of \(n\) distinct symbols and a 1-based index \(k\), we want the \(k\)-th lexicographic permutation. Generating every permutation up to the target would be wasteful, because \(10!=3{,}628{,}800\). The key fact is that lexicographic order is organized into factorial-sized blocks, so the desired permutation can be addressed directly from its rank. Mathematical Approach Let the available symbols be \(A=\{a_0<a_1<\cdots<a_{n-1}\}\), and let \(r=k-1\) be the 0-based rank. The entire method is a repeated answer to one question: which block of size \((m-1)!\) contains the target permutation when \(m\) symbols remain? Factorial-Sized Lexicographic Blocks Fix the first symbol of a permutation of \(m\) distinct symbols. The remaining \(m-1\) symbols can then be arranged in exactly \((m-1)!\) ways. Therefore the lexicographic list splits into consecutive blocks of size \((m-1)!\), one block for each possible first symbol in sorted order. If the current 0-based rank is \(r\), then the correct block number is $$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor,$$ so the next symbol is the \(q\)-th smallest unused symbol....

Detailed mathematical approach

Problem Summary

The problem asks for the millionth permutation of the digits \(0,1,2,\dots,9\) when all \(10!\) permutations are listed in lexicographic order. More generally, given any ordered set of \(n\) distinct symbols and a 1-based index \(k\), we want the \(k\)-th lexicographic permutation.

Generating every permutation up to the target would be wasteful, because \(10!=3{,}628{,}800\). The key fact is that lexicographic order is organized into factorial-sized blocks, so the desired permutation can be addressed directly from its rank.

Mathematical Approach

Let the available symbols be \(A=\{a_0<a_1<\cdots<a_{n-1}\}\), and let \(r=k-1\) be the 0-based rank. The entire method is a repeated answer to one question: which block of size \((m-1)!\) contains the target permutation when \(m\) symbols remain?

Factorial-Sized Lexicographic Blocks

Fix the first symbol of a permutation of \(m\) distinct symbols. The remaining \(m-1\) symbols can then be arranged in exactly \((m-1)!\) ways. Therefore the lexicographic list splits into consecutive blocks of size \((m-1)!\), one block for each possible first symbol in sorted order.

If the current 0-based rank is \(r\), then the correct block number is

$$q=\left\lfloor \frac{r}{(m-1)!} \right\rfloor,$$

so the next symbol is the \(q\)-th smallest unused symbol. After choosing it, the rank inside that block becomes

$$r'=r\bmod (m-1)!.$$

A Recursive Rank-to-Permutation Rule

This gives a clean recurrence. If \(T(A,r)\) denotes the permutation of rank \(r\) among the symbols in \(A\), and if \(A=\{a_0<\cdots<a_{m-1}\}\), then with \(q=\lfloor r/(m-1)!\rfloor\) and \(r'=r\bmod (m-1)!\),

$$T(A,r)=a_q\text{ followed by }T(A\setminus\{a_q\},r').$$

The base case is \(T(\{a\},0)=a\). The invariant is simple and crucial: after fixing a prefix, the updated rank is always the lexicographic rank of the remaining suffix among the remaining unused symbols.

Factoradic and Lehmer Code Interpretation

The same procedure can be written as a factorial-number-system expansion:

$$r=c_{n-1}(n-1)!+c_{n-2}(n-2)!+\cdots+c_1 1!+c_0 0!,$$

with \(0\le c_i\le i\). These coefficients are unique. At step \(i\), the coefficient \(c_i\) tells us which remaining symbol to take from the sorted pool. In permutation language, \((c_{n-1},c_{n-2},\dots,c_0)\) is the Lehmer code of the answer.

This viewpoint explains why no backtracking is needed: each quotient fixes one position permanently, and each remainder passes the unresolved part of the problem to the next smaller factorial scale.

Worked Example: The Millionth Permutation

For the original problem we convert from 1-based to 0-based rank:

$$r=1{,}000{,}000-1=999{,}999.$$

Its factoradic expansion is

$$999{,}999=2\cdot 9!+6\cdot 8!+6\cdot 7!+2\cdot 6!+5\cdot 5!+1\cdot 4!+2\cdot 3!+1\cdot 2!+1\cdot 1!+0\cdot 0!.$$

So we choose, in order, the \(2\)-nd, \(6\)-th, \(6\)-th, \(2\)-nd, \(5\)-th, \(1\)-st, \(2\)-nd, \(1\)-st, \(1\)-st, and \(0\)-th remaining digits. Starting from \([0,1,2,3,4,5,6,7,8,9]\), those choices produce

$$2,\ 7,\ 8,\ 3,\ 9,\ 1,\ 5,\ 4,\ 6,\ 0,$$

hence the millionth lexicographic permutation is

$$2783915460.$$

How the Code Works

The C++, Python, and Java implementations accept a symbol string and a 1-based permutation index, then sort the symbols so that lexicographic order is defined unambiguously. They compute \(n!\) for the symbol count and reject any request outside the valid range \(1\le k\le n!\).

After that, the implementation converts \(k\) to the 0-based rank \(r=k-1\), stores the remaining symbols in a mutable ordered pool, and repeats the quotient-remainder step. At each round it divides by \((m-1)!\), uses the quotient as an index into the pool, appends the chosen symbol to the answer, removes it from the pool, and continues with the remainder.

The implementations also include small checkpoints such as the first and last permutations of the symbols \(0,1,2\), which verify that the ordering and the off-by-one convention are correct before solving the main case.

Complexity Analysis

There are \(n\) selection rounds. In these implementations the remaining symbols are kept in a simple list or array-like structure, so removing the chosen symbol costs \(O(n)\) in the worst case. The total running time is therefore \(O(n^2)\), and the extra space is \(O(n)\).

For the original input \(n=10\), this cost is tiny. The important gain is conceptual: the algorithm computes one target permutation directly instead of enumerating all \(10!\) permutations that come before it.

Footnotes and References

  1. Problem page: https://projecteuler.net/problem=24
  2. Factorial number system: https://en.wikipedia.org/wiki/Factorial_number_system
  3. Lehmer code: https://en.wikipedia.org/wiki/Lehmer_code
  4. Lexicographical order: https://en.wikipedia.org/wiki/Lexicographical_order
  5. Permutation: https://en.wikipedia.org/wiki/Permutation

Problem 24 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    u64 index = 1000000ULL;
    std::string digits = "0123456789";
    bool run_checkpoints = true;
};

bool parse_u64_after_prefix(const std::string& arg, const std::string& prefix, u64& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    u64 parsed = 0ULL;
    for (const char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        const u64 digit = static_cast<u64>(c - '0');
        if (parsed > (std::numeric_limits<u64>::max() - digit) / 10ULL) {
            return false;
        }
        parsed = parsed * 10ULL + digit;
    }

    value = parsed;
    return true;
}

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    value = tail;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_u64_after_prefix(arg, "--index=", options.index)) {
            continue;
        }
        if (parse_string_after_prefix(arg, "--digits=", options.digits)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.index >= 1ULL && !options.digits.empty();
}

u64 factorial(const std::size_t n) {
    u64 value = 1ULL;
    for (std::size_t k = 2; k <= n; ++k) {
        if (value > std::numeric_limits<u64>::max() / static_cast<u64>(k)) {
            throw std::overflow_error("factorial overflow");
        }
        value *= static_cast<u64>(k);
    }
    return value;
}

std::string nth_lexicographic_permutation(std::string digits, u64 index_one_based) {
    std::sort(digits.begin(), digits.end());
    const std::size_t n = digits.size();

    const u64 total = factorial(n);
    if (index_one_based < 1ULL || index_one_based > total) {
        throw std::runtime_error("Permutation index out of range");
    }

    u64 rank = index_one_based - 1ULL;
    std::string answer;
    answer.reserve(n);

    std::vector<char> pool(digits.begin(), digits.end());

    for (std::size_t remaining = n; remaining > 0; --remaining) {
        const u64 block = factorial(remaining - 1);
        const u64 pick = rank / block;
        rank %= block;

        answer.push_back(pool[static_cast<std::size_t>(pick)]);
        pool.erase(pool.begin() + static_cast<std::ptrdiff_t>(pick));
    }

    return answer;
}

std::string solve(const Options& options) {
    return nth_lexicographic_permutation(options.digits, options.index);
}

bool run_checkpoints() {
    if (nth_lexicographic_permutation("012", 1ULL) != "012") {
        std::cerr << "Checkpoint failed for first permutation" << '\n';
        return false;
    }
    if (nth_lexicographic_permutation("012", 6ULL) != "210") {
        std::cerr << "Checkpoint failed for last permutation" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

import sys
from typing import List, Tuple


def factorial(n: int) -> int:
    value = 1
    for k in range(2, n + 1):
        if value > sys.maxsize // k:
            raise OverflowError("factorial overflow")
        value *= k
    return value


def nth_lexicographic_permutation(digits: str, index_one_based: int) -> str:
    sorted_digits = sorted(digits)
    n = len(sorted_digits)

    total = factorial(n)
    if index_one_based < 1 or index_one_based > total:
        raise RuntimeError("Permutation index out of range")

    rank = index_one_based - 1
    answer = []
    pool = list(sorted_digits)

    for remaining in range(n, 0, -1):
        block = factorial(remaining - 1)
        pick = rank // block
        rank %= block

        answer.append(pool[pick])
        del pool[pick]

    return ''.join(answer)


def solve(index: int, digits: str) -> str:
    return nth_lexicographic_permutation(digits, index)


def run_checkpoints() -> bool:
    if nth_lexicographic_permutation("012", 1) != "012":
        return False
    if nth_lexicographic_permutation("012", 6) != "210":
        return False
    return True


def parse_arguments(args: List[str]) -> Tuple[int, str, bool]:
    index = 1000000
    digits = "0123456789"
    run_checkpoints_flag = True

    i = 1
    while i < len(args):
        arg = args[i]

        if arg == "--skip-checkpoints":
            run_checkpoints_flag = False
            i += 1
            continue

        if arg.startswith("--index="):
            try:
                index = int(arg[8:])
                if index < 1:
                    raise ValueError()
            except ValueError:
                print(f"Invalid argument: {arg}", file=sys.stderr)
                sys.exit(1)
            i += 1
            continue

        if arg.startswith("--digits="):
            digits = arg[9:]
            if not digits:
                print(f"Invalid argument: {arg}", file=sys.stderr)
                sys.exit(1)
            i += 1
            continue

        print(f"Unknown argument: {arg}", file=sys.stderr)
        sys.exit(1)

    if index < 1 or not digits:
        print("Invalid arguments", file=sys.stderr)
        sys.exit(1)

    return index, digits, run_checkpoints_flag


def main():
    args = sys.argv[1:]
    
    index, digits, run_checkpoints_flag = parse_arguments(args)

    if run_checkpoints_flag and not run_checkpoints():
        print("Checkpoint failed", file=sys.stderr)
        sys.exit(2)

    try:
        result = solve(index, digits)
        print(result)
    except Exception as ex:
        print(str(ex), file=sys.stderr)
        sys.exit(3)


if __name__ == "__main__":
    main()

Java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Euler24 {

    private static class Options {
        long index = 1000000L;
        String digits = "0123456789";
        boolean runCheckpoints = true;
    }

    private static boolean parseULongAfterPrefix(String arg, String prefix, long[] valueRef) {
        if (!arg.startsWith(prefix)) {
            return false;
        }
        String tail = arg.substring(prefix.length());
        if (tail.isEmpty()) {
            return false;
        }

        long parsed = 0L;
        for (int i = 0; i < tail.length(); i++) {
            char c = tail.charAt(i);
            if (c < '0' || c > '9') {
                return false;
            }
            int digit = c - '0';
            if (parsed > (Long.MAX_VALUE - digit) / 10L) {
                return false;
            }
            parsed = parsed * 10L + digit;
        }

        valueRef[0] = parsed;
        return true;
    }

    private static boolean parseStringAfterPrefix(String arg, String prefix, String[] valueRef) {
        if (!arg.startsWith(prefix)) {
            return false;
        }
        String tail = arg.substring(prefix.length());
        if (tail.isEmpty()) {
            return false;
        }
        valueRef[0] = tail;
        return true;
    }

    private static boolean parseArguments(String[] args, Options options) {
        for (String arg : args) {
            if ("--skip-checkpoints".equals(arg)) {
                options.runCheckpoints = false;
                continue;
            }

            long[] indexRef = new long[1];
            if (parseULongAfterPrefix(arg, "--index=", indexRef)) {
                options.index = indexRef[0];
                continue;
            }

            String[] digitsRef = new String[1];
            if (parseStringAfterPrefix(arg, "--digits=", digitsRef)) {
                options.digits = digitsRef[0];
                continue;
            }

            System.err.println("Unknown argument: " + arg);
            return false;
        }

        return options.index >= 1L && !options.digits.isEmpty();
    }

    private static long factorial(int n) {
        long value = 1L;
        for (int k = 2; k <= n; k++) {
            if (value > Long.MAX_VALUE / k) {
                throw new RuntimeException("factorial overflow");
            }
            value *= k;
        }
        return value;
    }

    private static String nthLexicographicPermutation(String digits, long indexOneBased) {
        char[] chars = digits.toCharArray();
        java.util.Arrays.sort(chars);
        String sortedDigits = new String(chars);
        int n = sortedDigits.length();

        long total = factorial(n);
        if (indexOneBased < 1L || indexOneBased > total) {
            throw new RuntimeException("Permutation index out of range");
        }

        long rank = indexOneBased - 1L;
        StringBuilder answer = new StringBuilder(n);

        List<Character> pool = new ArrayList<>();
        for (char c : sortedDigits.toCharArray()) {
            pool.add(c);
        }

        for (int remaining = n; remaining > 0; remaining--) {
            long block = factorial(remaining - 1);
            int pickIndex = (int)(rank / block);
            rank %= block;

            answer.append(pool.get(pickIndex));
            pool.remove(pickIndex);
        }

        return answer.toString();
    }

    private static String solve(Options options) {
        return nthLexicographicPermutation(options.digits, options.index);
    }

    private static boolean runCheckpoints() {
        if (!nthLexicographicPermutation("012", 1L).equals("012")) {
            System.err.println("Checkpoint failed for first permutation");
            return false;
        }
        if (!nthLexicographicPermutation("012", 6L).equals("210")) {
            System.err.println("Checkpoint failed for last permutation");
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Options options = new Options();
        if (!parseArguments(args, options)) {
            System.exit(1);
        }

        if (options.runCheckpoints && !runCheckpoints()) {
            System.exit(2);
        }

        try {
            System.out.println(solve(options));
        } catch (Exception ex) {
            System.err.println(ex.getMessage());
            System.exit(3);
        }

        System.exit(0);
    }
}