Problem 24 "Lexicographic permutations"

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?

問 24 「辞書式順列」

順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると

012 021 102 120 201 210

になる.

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか?

fn factorial(n: u64) -> u64 {
    match n {
        0 | 1 => 1,
        _ => factorial(n - 1) * n,
    }
}

fn main() {
    let mut reminder = 1_000_000u64 - 1;
    let mut items_with_order = vec![0u64, 1, 2, 3, 4, 5, 6, 7, 8, 9];
    let mut millionth_element = 0u64;
    for weight in (0..items_with_order.len()).rev() {
        let unit = factorial(weight as u64);
        let quot = reminder / unit;
        reminder -= quot * unit;
        millionth_element *= 10;
        millionth_element += items_with_order.remove(quot as usize);
    }

    println!("{}", millionth_element);
    assert_eq!(millionth_element, 2783915460);
}