오일러 프로젝트 24 (Julia)

0,1,2,3,4,5,6,7,8,9로 만들 수 있는 1백만 번째의 사전식 순열을 구하는 문제이다. n개의 요소에 대해 만들 수 있는 순열의 가지수는 n! 가지이다. 10개의 숫자로 순열을 만들 때, 첫자리를 0으로 정했다면 9! 가지의 순열을 생성할 수 있다. 따라서 999,999를 9!로 나눈 몫이 첫 번째 숫자가 될 것이다. 그 나머지에 대해서도 동일하게 8!로 나눠서 두 번째 숫자를 정할 수 있다. 이 과정을 반복하여 나머지가 더 이상 남지 않을 때까지 반복하면 1백만번째 순열을 구할 수 있다. 이 때 백만이 아니라 999,999를 한계값으로 사용하는 것은 0123456789가 0번째에 해당하기 때문이다.

이를 일반화하여 집합에서 n번째 순열을 구하는 방법을 다음과 같이 구할 수 있다.

function nthperm(xs, n)
    n = (n - 1) % factorial(length(xs))
    res = []
    while length(xs) > 0
        q, r = divrem(n, factorial(length(xs) - 1))
        push!(res, xs[q+1])
        xs = [xs[1:q]; xs[q+2:end]]
        n = r
    end
    return res
end

function s024()
    nthperm(0:9, 1_000_000) |> join |> println
end


@time s024()