Словарные перестановки

Перестановка - это упорядоченная выборка объектов. К примеру, 3124 является одной из возможных перестановок из цифр 1, 2, 3 и 4. Если все перестановки приведены в порядке возрастания или алфавитном порядке, то такой порядок будем называть словарным. Словарные перестановки из цифр 0, 1 и 2 представлены ниже:

012 021 102 120 201 210

Какова миллионная словарная перестановка из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9?

Решение (F#)

Решение основано на предположении что все цифры находятся на определенном месте одинаковое количество раз

• всего возможно 10! = 3 628 800 перестановок
• т.е. число 0 будет стоять первым ровно 362 880 раз
• число 1 - столько же
• значит миллионный элемент будет иметь первым числом 2
• ставим число 2 на первое место, остальные числа, от меньшего к большему расставляем аналогично
• fact - функция вычисления факториала
• loop - рекурсивная функция вычисления n-ой перестановки списка, согласно приведенному выше алгоритму

let solv =
    let fact n = seq { 1..n } |> Seq.reduce (*)

    let rec loop acc (curr: int list) (left: int) =
        match curr.Length with
        | 0 -> acc
        | 1
        | _ when left = 0 -> acc @ curr
        | _ ->
            let l = fact (curr.Length - 1)
            let n = left / l
            let d = List.item n curr
            loop (acc @ [ d ]) (List.removeAt n curr) (left - n * l)

    loop [] [ 0..9 ] 1000000

printfn "the answer is %A" solv //the answer is [2; 7; 8; 3; 9; 1; 5; 6; 0; 4]