順列を一瞬で取得するプログラム
https://itakanaya9.hatenablog.com/entry/2014/02/17/121428
を Julia に移植する。
function nthpermutation(x, k)
k -= 1
result = x
if k > 0
x = copy(x)
n = length(x)
reminder = zeros(Int, n)
for i = 1:n
reminder[i] = k % i + 1
k ÷= i
end
for i = 1:n
at = reminder[n-i+1]
result[i] = x[at]
deleteat!(x, at)
end
end
return result
end
function nthpermutation(x)
n = length(x)
nrow = factorial(n)
result = fill(x[1], nrow, n)
for i = 1:nrow
result[i, :] = nthpermutation(x, i)
end
return result
end
x = ["A", "B", "C", "D"]
nthpermutation(x, 10)
#=
4-element Vector{String}:
"B"
"C"
"D"
"A"
=#
x がどんな型でも，同じ型の結果を返す（当たり前だが）
x = collect(1:3)
for i = 1:factorial(length(x))
println("$i, $(nthpermutation(x, i))")
end
#=
1, [1, 2, 3]
2, [1, 3, 2]
3, [2, 1, 3]
4, [2, 3, 1]
5, [3, 1, 2]
6, [3, 2, 1]
=#
引数が 1 つだと，全ての順列を返す関数が呼ばれる。
nthpermutation(x)
#=
6×3 Matrix{Int64}:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
=#
x が重複する要素を持つ場合も，重複した順列を返すので注意。
a = nthpermutation([false, false, true, true, true])
重複を省いた結果を求める場合は unique() を使う。
unique(a, dims=1)
#=
10×5 Matrix{Bool}:
0 0 1 1 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 1 0 1
1 0 1 1 0
1 0 0 1 1
1 1 0 1 0
1 1 0 0 1
1 1 1 0 0
=#
k が大きかろうが小さかろうが，計算時間は同じ。
10 個の要素の最後の順列は 3628800 番目であるが，計算は瞬時。
@time nthpermutation(collect(1:10), 3628800)
#=
0.000003 seconds (4 allocations: 640 bytes)
10-element Vector{Int64}:
10
9
8
7
6
5
4
3
2
1
=#
実は，Conbinatrics の nthperm は同じことをしている（コーディングは洗練されているが）
using Combinatorics
@time nthperm(collect(1:10), 3628800)
#=
0.000004 seconds (2 allocations: 320 bytes)
10-element Vector{Int64}:
10
9
8
7
6
5
4
3
2
1
=#
ほとんど同じ計算時間である。
