前回は組み合わせの総数を求めた。
今回は組み合わせのパターンを求める。
いやー、yield return 便利ですね。
組み合わせ
多分中学くらいで学ぶやつ。
例題
例として「1から4が書かれた4枚のカードがある。3枚の組み合わせを全部書き出しなさい」という問題を出されたとする。
[1, 2, 3, 4]のカードから3枚を選ぶ組み合わせは、次の4通り。
[1, 2, 3] [1, 2, 4] [1, 3, 4] [2, 3, 4]
重要なのは「組み合わせ」であって、「順序」は関係ないということ。
[1, 2, 3] のカードの組は [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2]と同じものと考える。
コード
考えてできあがったのがコレ。
using System.Numerics; public partial class MathPlus { public class Combination { /// <summary> /// 要素の個数 /// </summary> private int _n; /// <summary> /// 選択する個数 /// </summary> private int _k; private int[] _elements; private int[] _idxset; /// <summary> /// 組み合わせの数 /// </summary> public BigInteger Count { get { return this.Combination_Count(); } } /// <summary> /// コンストラクタ /// </summary> /// <param name="n">要素の個数</param> /// <param name="k">選択する個数</param> public Combination(int n, int k) { this._n = n; this._k = k; this._elements = Enumerable.Range(1, this._n).ToArray(); this._idxset = Enumerable.Range(0, this._k).ToArray(); } /// <summary> /// 組み合わせの数を求める /// </summary> /// <returns>組み合わせの数</returns> private BigInteger Combination_Count() { var numerator = new BigInteger(1); var denominator = new BigInteger(1); var n = this._n; var k = this._k; var tmp = 1L; if (this._k > this._n - this._k) k = this._n - this._k; for (int count = 1; count <= k; count++) { numerator *= n; n--; denominator *= tmp; tmp++; } return numerator / denominator; } /// <summary> /// 組み合わせパターンを得る /// </summary> /// <returns>組み合わせパターンの反復子</returns> public IEnumerable<int[]> GetEnumerable() { if (this._idxset.Length == 0) yield break; while (this._idxset[this._idxset.Length - 1] != this._n) { yield return this.Result(); Update(); } yield break; } /// <summary> /// 参照の更新 /// </summary> private void Update() { for (int i = this._idxset.Length - 1; i >= 0; i--) { if (this._idxset[i] != this._n) { this._idxset[i]++; for (int r = i + 1; r < this._idxset.Length; r++) { this._idxset[r] = this._idxset[r - 1] + 1; } } if (this._idxset[this._idxset.Length - 1] != this._n) break; } } /// <summary> /// 組み合わせパターンの生成 /// </summary> /// <returns>組み合わせパターン</returns> private int[] Result() { List<int> c = new List<int>(); foreach (var i in this._idxset) c.Add(this._elements[i]); return c.ToArray(); } } }
Program.csをこんなふうに書いて実行する。
var combination = new MathPlus.Combination(5, 3); foreach (var item in combination.GetEnumerable()) { Console.WriteLine($"[{string.Join(",", item)}]"); Thread.Sleep(100); } Console.WriteLine(($"個数:{combination.Count}"));
実行結果
[1,2,3] [1,2,4] [1,2,5] [1,3,4] [1,3,5] [1,4,5] [2,3,4] [2,3,5] [2,4,5] [3,4,5] 個数:10
なぜよくある再帰を使用したコードにしないの？
コピペしてC(400000, 1000)を計算させたらメモリバカ食いして死んだから。
説明
説明書こうとしたものの、めんどくさくなったので省いたけど書いたほうがいいのかな？
まずコンストラクタが呼び出される。
/// <summary> /// コンストラクタ /// </summary> /// <param name="n">要素の個数</param> /// <param name="k">選択する個数</param> public Combination(int n, int k) { this._n = n; this._k = k; this._elements = Enumerable.Range(1, this._n).ToArray(); this._idxset = Enumerable.Range(0, this._k).ToArray(); }
ここで1からnの要素が入ってる配列 elements と、要素の参照する場所を格納したサイズkの配列 idxset を作る。
C(5, 3)だと次のような初期値になる。
| elements | 1 | 2 | 3 | 4 | 5 |
| idxset | 0 | 1 | 2 |
idxset は elements に対する参照の集合なので、
idxset[0](値は0) は elements[0](値は1)
idxset[2](値は2) は elements[2](値は3) を指し示す。
仮に idxset[2]の値が4だと elements[4] の値5になる。
インデックス(index)の集合(set)だからidxsetなんていう名前にしたけど、もっと他にいい名前があるかもしれない。
idxset をサイズ k で確保してることから感の鋭い諸兄におかれましては既にお分かりの通り、 idxset を使って「組み合わせ」が作られます。
次にコイツが来る。
/// <summary> /// 組み合わせパターンを得る /// </summary> /// <returns>組み合わせパターンの反復子</returns> public IEnumerable<int[]> GetEnumerable() { if (this._idxset.Length == 0) yield break; while (this._idxset[this._idxset.Length - 1] != this._n) { yield return this.Result(); Update(); } yield break; }
yield break や yield return はマイクロソフトのサイトを参考にしてもらうとする。
learn.microsoft.com
まず最初に idxset.Length が0、 つまりidxsetのサイズが0の時は何もせずに即終了宣言。
参照が無いならどうにもならんし。
次にwhileループに入る。
ループ条件は「idxsetの配列のケツが n と同じではない」こと。
C(n, k) = C(5, 3) の場合
- idxsetの配列の最後尾が5 => ループ終了
- idxsetの配列の最後尾が5以外 => ループ継続
ということになる。
最初の関門を通り抜けると Result による出力。
idxsetの値を頭から参照していく。
| index | 0 | 1 | 2 | 3 | 4 |
| elements | 1 | 2 | 3 | 4 | 5 |
| idxset | 0 | 1 | 2 |
今は[0][1][2]なので、elements の index [0][1][2]を参照し [1][2][3] を結果として返す。
次に idxset を更新するための Update に入る。
/// <summary> /// 参照の更新 /// </summary> private void Update() { for (int i = this._idxset.Length - 1; i >= 0; i--) { if (this._idxset[i] != this._n) { this._idxset[i]++; for (int r = i + 1; r < this._idxset.Length; r++) { this._idxset[r] = this._idxset[r - 1] + 1; } } if (this._idxset[this._idxset.Length - 1] != this._n) break; } }
一番外側のforによってidxsetを最後尾から見ていく。
状態はこう。
| index | 0 | 1 | 2 |
| idxset | 0 | 1 | 2 |
i : 2
idxset[i] : 2
まず idxset[i] が n になってないか確認する。
C(n, k) = C(5, 3) なので n は5、対する idxset[i] は2なので idxset[i] != n はtrueとなりifの中に入る。
ifの中ではまず最初に idxset[i] の値に1加える。
| index | 0 | 1 | 2 |
| idxset | 0 | 1 | 3 |
i : 2
idxset[i] : 3
次に i より後ろの配列を idxset[i]+1 から始まる値で昇順で更新する。
今は i : 2 であり、idxset の index に2以上はないので何もせず抜ける。
ifを抜ければ idxset の最後尾が n になってないか再び確認。
nならばforを続行、nでないならforを抜ける。
最初のアップデートが終わった時点でこうなる。
| index | 0 | 1 | 2 | 3 | 4 |
| elements | 1 | 2 | 3 | 4 | 5 |
| idxset | 0 | 1 | 3 |
whileに戻り、idxsetの最後尾がn(5)ではないのでループ続行、出力を行う。
idxsetが[0][1][3]なので、elementsのindexを参照し出力は[1][2][4]となる。
再びUpdateを通り抜けるとidxsetが更新され[0][1][4]となり、[1][2][5]が出力となる。
次にUpdateに入ると最後尾に+1されidxsetは[0][1][5]。
idxsetの最後尾が5なのでbreakに到達せずforループが回り、iの値が1減り i : 1 となる。
idxset[i]に1を加える処理が走ってこうなる。
| index | 0 | 1 | 2 |
| idxset | 0 | 2 | 5 |
i : 1
idxset[i] : 2
iより後ろにidxset[i]+1から始まる整数を昇順で入れていく処理が入り、こうなる。
| index | 0 | 1 | 2 |
| idxset | 0 | 2 | 3 |
再び最後尾が5でないかどうかの判定が来て、5でないのでループを抜ける。
| index | 0 | 1 | 2 | 3 | 4 |
| elements | 1 | 2 | 3 | 4 | 5 |
| idxset | 0 | 2 | 3 |
そしてidxsetを参照にして出力は[1][3][4]となる。
後は同じ処理をぐるぐるやって全部吐き出す。
書いててidxsettというかelementsいらんような気がしてきた…
