【ITニュース解説】Como Penso e Resolvo "Count Ways to Distribute Candies" em Elixir (Corrigido)

n個のユニークなキャンディーとk個の袋がある時、全てのキャンディーを袋に配り、どの袋も空にしない、つまり最低でも1つはキャンディーが入っているようにする方法が何通りあるかを計算する問題だ。ここでキャンディーはそれぞれが違うものとして扱われ、袋自体は区別しない。例えば、3つのキャンディーを2つの袋に分ける場合、(1), (2,3) と (1,2), (3) と (1,3), (2) の3通りが存在する。

この問題は、数学の分野では「集合の分割」と呼ばれる概念と密接に関係している。具体的には、「n個の要素を持つ集合を、ちょうどk個の空ではない部分集合に分割する方法の数」を求めることと同じであり、この特別な数は「第二種スターリング数」と呼ばれ、S(n, k)と表記される。

このような組み合わせの問題を効率的に解くためには、「動的計画法（DP）」という手法が用いられる。これは、問題をより小さな部分問題に分割し、その結果を利用して解を導く方法だ。第二種スターリング数には、S(n, k) = k × S(n-1, k) + S(n-1, k-1) という漸化式（繰り返し計算できる式）が存在する。この式は、n番目のキャンディーに着目することで導き出せる。n番目のキャンディーを他のキャンディーとは別の新しい袋に入れる場合、残りのn-1個のキャンディーをk-1個の袋に分ける方法はS(n-1, k-1)通りある。また、n番目のキャンディーをすでに他のキャンディーが入っている既存のk個の袋のどれかに入れる場合、残りのn-1個のキャンディーはk個の袋に分けられており、n番目のキャンディーはそのk個の袋のどれか一つに追加されるので、その選択肢はk通り存在する。よって、方法はk × S(n-1, k)通りとなる。これら二つのケースを合計すると上記の漸化式になる。

この漸化式を動的計画法で計算する際、計算結果を保存するテーブルのようなデータ構造が必要となる。多くのプログラミング言語では、このテーブルとして「配列（array）」が使われ、特定の場所（インデックス）にあるデータを非常に高速に（一定の時間で）読み書きできる特性を持つ。しかし、Elixirという言語で同様に考えると、思わぬ落とし穴にはまることがある。

Elixirにおいて、角括弧 [] で表現されるデータ構造は、一般的な言語の配列とは異なり、「連結リスト（linked list）」という種類だ。連結リストでは、データが鎖のように繋がっており、先頭から順にしかたどることができない。そのため、リストの途中や最後にあるデータにアクセスするには、先頭から目的の場所まで全ての要素を一つずつたどっていく必要があり、リストの長さLに対してアクセスに最大でLの時間がかかる（計算量で言うとO(L)）。同様に、リストの途中の要素を更新しようとすると、その場所までたどってから、変更箇所以降の全ての要素を新しく作り直す必要があり、これもまたO(L)の時間がかかってしまう。

したがって、動的計画法でElixirのリストを「配列」の代わりとして使い、頻繁にインデックスアクセスや更新を行うと、期待していたよりもはるかに遅いプログラムになってしまう。例えば、DPテーブルの各行を計算するのにk回の更新が必要だとすると、O(k)の時間のかかる操作をk回行うことになるため、1行あたりO(k²)の時間を使ってしまう。これをn行分繰り返すと、全体の計算時間はO(n × k²)となり、非効率的だ。元の漸化式を素直に実装すればO(n × k)で済むはずだったのに、データ構造の選択ミスで性能が大きく劣化してしまうのだ。

ではElixirで、配列のように高速なインデックスアクセスが可能なデータ構造は何だろうか。それは波括弧 {} で表現される「タプル（tuple）」だ。タプルは、一度作成されると要素の数が固定される性質を持つ。Elixirのタプルは、特定のインデックスにある要素にO(1)（一定の時間）でアクセスできる。これは配列と同じ利点だ。しかし、タプルにも注意点があり、タプルの途中の要素を更新する put_elem という操作は、実は新しいタプル全体を作り直す必要があるため、タプルの長さLに対してO(L)の時間がかかってしまう。

そのため、タプルを使った動的計画法の実装では、各ステップで複数の要素を一つずつ更新するのではなく、新しい行の計算結果を一度にまとめて新しいタプルとして生成する工夫が必要になる。具体的には、前の行のタプルを参照しながら、新しい行の全ての要素を計算し、それらを一度にリストとして生成してから、そのリストをタプルに変換する方法をとる。この方法であれば、1行あたりの計算時間をO(k)に抑えられ、全体として望ましいO(n × k)の計算時間で問題を解くことができる。

この効率的なタプルを使った実装では、各ステップでk+1個の要素を持つタプルを更新していくため、時間計算量はn回繰り返される各ステップでO(k)かかり、合計でO(n × k)となる。空間計算量については、現在の行と前の行の2つのタプルだけをメモリに保持すれば良いので、O(k)となる。これは、nとkが1000程度の範囲であっても十分に高速に動作する。

比較のために、Elixirにはキーと値を関連付けてデータを保存する「マップ（map）」というデータ構造もある。マップは柔軟だが、インデックスアクセスや更新にかかる時間は平均してO(log k)となる。そのため、DPでマップを使うと全体の計算時間はO(n × k × log k)となり、タプルを使った方法よりも若干遅くなる可能性がある。

この「キャンディー分配問題」は、単なる組み合わせ計算の練習問題に留まらない。この問題を通じて、第二種スターリング数という数学的な概念と、それを効率的に計算するための動的計画法を学ぶことができる。しかし、最も重要な教訓は、Elixirのような関数型言語でプログラミングを行う際、「データ構造の選択」がいかに重要か、ということだ。従来の命令型言語での常識（配列は高速なインデックスアクセスを持つ）がElixirのリストには当てはまらないこと、そしてタプルがその代替となり得るが、その使い方にも工夫が必要であることを理解することは、Elixirを習得する上で非常に価値のある学びとなる。適切なデータ構造を適切な方法で使うことが、効率的なプログラムを書くための鍵なのだ。