組み合わせを列挙する

この記事で扱っていること

を紹介しています。

注意：すべてのエラーを確認しているわけではないので、記事の内容を実装する際には自己責任でお願いします。また、エラー配線は適当な部分があるので適宜修正してください。

何か複数の入力値に対して、それらの組み合わせのパターンを列挙する方法を考えました。数学でいうところの、コンビネーション、のことになりますが、ただ単純にコンビネーションの数を求めるのではなく（それは解析的にできるので）、具体的な組み合わせの内容をすべて列挙する、ということになります。

例えば、6個の中から2個を選ぶ組み合わせの総数を考える場合、6個の要素がA、B、C、D、E、Fだったとして

[A,B]、[A,C]、[A,D]、[A,E]、[A,F]、[B,C]、[B,D]、[B,E]、[B,F]、[C,D]、[C,E]、[C,F]、[D,E]、[D,F]、[E,F]の15通りです。

今回のプログラムでは、この「15」という数字を求めるのではなく、[A,B]から[E,F]までの具体的な候補を挙げていきます。

なお、処理としては、「6個の中から2個」だけでなく、全ての組み合わせ（「6個の中からN個」だったとした場合のN=1~６）を出し、記事後半でNを一つ決めた場合の候補に絞る方法を紹介します。

なお、記事後半でも触れますが、今回紹介している方法の実用的な上限としては、組み合わせを確認する対象の配列の要素数がせいぜい25個程度の場合となります。

どんな結果になるか

抽出する対象となる要素は配列で用意しておきます。

データタイプは文字列としています（数値の配列に対して同じことをしたい場合には、それら数値を文字列に変換すれば同じプログラムが使えます）。

プログラムを実行すると、全ての組み合わせを列挙します。

こういった処理は本来再帰的に行う方が効率がいいことと思います。

ただし、プログラムの中で、「M個中のN個」の「N」の部分をいくつか変える必要がある場合には、最初から全組み合わせを計算しておいて、あとから特定のNを指定したときの結果を抽出するというやり方が便利なときもあります。

ブロックダイアグラムとしては以下のようにしました。

外側のForループが回るたびに、シフトレジスタでまわしているresult文字列配列の要素の数が倍々で増えていくのがわかると思います。

ある反復終了時のresult文字列配列の要素をシフトレジスタで次の反復に渡し、その反復時に内側のForループで新しい要素を追加していきます。

内側のForループが終わったら、「内側のForループの処理を行っていない」配列と合わせるために配列連結追加します。

文字だけだとわかりづらいかもしれませんが、紙に書きながらプログラムを追うと理解しやすいと思います。

Forループを出た後、配列から削除の関数を使っているのは、「1つも選ばれない」場合を除くためです。

上では全組み合わせを列挙しましたが、「6個中2個」のような、何個とるかが決まっている場合には、抽出処理を入れます。

カンマで要素を区切っているので、このカンマの数を利用します。

上のプログラムを見て、「これって処理どれくらいかかるの？」と疑問に思われる方もいると思います。

全ての組み合わせを列挙している関係上、対象となる配列の要素数がMだとすると、そのM個の要素を含む、含まないの2択をM回行うことになるので、処理数は2のM乗オーダーになります。（一つも要素を含まない場合を除くので組み合わせ数は2のM乗引く1）

実際に要素数がどの程度でどれくらいの時間がかかるのかについて簡単に調べてみました。

結果は以下に示した通りで、M=25のときに13秒ほどかかりました。

XYグラフを見てもわかると思いますが、文字通り指数関数的に処理時間が増えます。

M=25よりも大きいMとなると時間がかかりすぎる・・・というより64 bitのLabVIEWであっても処理しきれずPCが落ちます。

M=25だとすると、2の25乗、3千万程度の候補全てを羅列する必要がある場合も少ないと思うので、全組み合わせを数え上げる必要がある場面において実用的な範囲では、上のプログラムで十分と言えそうです。

本記事では組み合わせを列挙する方法を紹介しました。

元の配列の要素数が多いと、処理は2のべき乗分だけ増えることになるので処理数の上限はあるものの、要素数が20程度であればほぼ一瞬で処理は終わるので、組み合わせ全列挙の方法を気軽に実装したい時などに参考になればと思います。

ここまで読んでいただきありがとうございました。