2020年12月26日

posts/2020-12-26diary

金曜の夜は夕飯食べたあと、気になってたこれをやった。

defmodule Main do
  def main do
    [n, k] = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
    list =
      1..n
      |> Enum.reduce([], fn _, acc ->
        line = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
        [line | acc]
      end)
      |> Enum.reverse()

    solve(n, k, list) |> IO.puts()
  end

  def solve(n, k, list) do
    (0..n-1)
    |> Enum.to_list()
    |> permutations()
    |> Enum.filter(fn path -> Enum.at(path, 0) == 0 end)
    |> Enum.map(fn path ->
      (0..n-1)
      |> Enum.reduce(0, fn i, acc ->
        now_point = Enum.at(path, i)
        next_point = if i == n - 1 do 0 else Enum.at(path, i + 1) end
        acc + Enum.at(Enum.at(list, now_point), next_point)
      end)
    end)
    |> Enum.filter(&(&1 == k))
    |> Enum.count()
  end

  def permutations([]), do: [[]]
  def permutations(list), do: for elm <- list, rest <- permutations(list -- [elm]), do: [elm | rest]
end

しょうじき、順列を生成するpermutations()の実装がパッと思いつかなくてググってしまった…。悔しいので詳しくみていく。

def permutations([]), do: [[]]
def permutations(list), do: for elm <- list, rest <- permutations(list -- [elm]), do: [elm | rest]

この実装を日本語で表せば「要素を1つ取り出し、残りの部分の順列を求めて、最初に取り出した1つを求めた順列それぞれの先頭に加える」となる（声に出して読めたね、というくらい当然）。

小さい具体的な例でこのアルゴリズムを考えてみたいが、その前に基本的なことをおさらいしておく。

[elm | rest]がどうなるか。先頭に要素を追加することになる。

iex(1)> elm = 1
1
iex(2)> rest = [2, 3, 4]
[2, 3, 4]
iex(3)> [elm | rest]
[1, 2, 3, 4]

list -- [elm]でリストから要素を引ける。

iex(1)> list = [1, 2, 3, 4]
[1, 2, 3, 4]
iex(2)> elm = 1
1
iex(3)> list -- [elm]
[2, 3, 4]

リスト内包表記でジェネレータが2つある時(x, y)の挙動。要するにx, y全ての組み合わせが生成される。

iex(1)> for x <- [1, 3, 5], y <- [2, 4, 6], do: IO.puts "#{x} - #{y}"
1 - 2
1 - 4
1 - 6
3 - 2
3 - 4
3 - 6
5 - 2
5 - 4
5 - 6

これを踏まえて、[1, 2, 3]の順列をこのアルゴリズムで生成するのを考えてみる。

再掲

def permutations([]), do: [[]]
def permutations(list), do: for elm <- list, rest <- permutations(list -- [elm]), do: [elm | rest]

要素を1つ取り出し、残りの部分の順列を求めて、最初に取り出した1つを求めた順列それぞれの先頭に加える
要素数2の順列を求めるとき、要素がswapされた形で2つの組み合わせできる
- これは、要素数2の配列をpermutations()に渡したとき、ジェネレーターによって最初の要素・次の要素がそれぞれ先頭に来る組み合わせが生成されるから
もちろんdef permutations([]), do: [[]]があることで再帰がちゃんと止まる

[1, 2, 3]を渡したときの処理の流れを書くとこんな感じになる。

(step1)最初に[1]と[2, 3]に分けて、[2, 3]の順列を考える
- [2, 3]の順列は、それ自体と要素をswapさせたものになる -> [2, 3], [3, 2]
- 最初に分けた[1]をそれぞれ先頭に加える -> [1, 2, 3], [1, 3, 2]
(step2)次に[2]と[1, 3]に分けて、[1, 3]の順列を考える
- [1, 3]の順列は、それ自体と要素をswapさせたものになる -> [1, 3], [3, 1]
- 最初に分けた[2]をそれぞれ先頭に加える -> [2, 1, 3], [2, 3, 1]
(step3)最後に[3]と[1, 2]に分けて、[1, 2]の順列を考える
- [1, 2]の順列は、それ自体と要素をswapさせたものになる -> [1, 2], [2, 1]
- 最初に分けた[3]をそれぞれ先頭に加える -> [3, 1, 2], [3, 2, 1]
以上を全部まとめたのが順列になる

要素が4つ以上ある場合でも再帰的に処理されるので結局上に書いた流れと同じになる。すごいね再帰。

こうやって小さい例で考えてみるととてもわかりやすいしなんということはないんだけど、それだけ洗練されているということだし、だからといって自分でシュッと書けるものでもない。まあ書けたからどうというものでもないかもしれないけど。ただ少なくともモヤモヤは晴れた。

本質=Nervesをやらずにこういう手遊びばっかりしているのは悪いとまでは言えないけど良いとも言えないので早く本質=Nervesをやる権利が欲しい（=ラズパイ3を回収したい）。