30 lines
815 B
Plaintext
30 lines
815 B
Plaintext
defmodule Permutation do
|
|
def derangements(n) do
|
|
list = Enum.to_list(1..n)
|
|
Enum.filter(permutation(list), fn perm ->
|
|
Enum.zip(list, perm) |> Enum.all?(fn {a,b} -> a != b end)
|
|
end)
|
|
end
|
|
|
|
def subfact(0), do: 1
|
|
def subfact(1), do: 0
|
|
def subfact(n), do: (n-1) * (subfact(n-1) + subfact(n-2))
|
|
|
|
def permutation([]), do: [[]]
|
|
def permutation(list) do
|
|
for x <- list, y <- permutation(list -- [x]), do: [x|y]
|
|
end
|
|
end
|
|
|
|
IO.puts "derangements for n = 4"
|
|
Enum.each(Permutation.derangements(4), &IO.inspect &1)
|
|
|
|
IO.puts "\nNumber of derangements"
|
|
IO.puts " n derange subfact"
|
|
Enum.each(0..9, fn n ->
|
|
:io.format "~2w :~9w,~9w~n", [n, length(Permutation.derangements(n)), Permutation.subfact(n)]
|
|
end)
|
|
Enum.each(10..20, fn n ->
|
|
:io.format "~2w :~19w~n", [n, Permutation.subfact(n)]
|
|
end)
|