C#で順列(Permutation)と組み合わせ(Combination)をすべて列挙してみよう
さて、いきなり少年メリケンサックですが、気にしないでください。帰らないでください。内容はまともです。
C#で順列(Permutation)を列挙する実装については、割と書いている人がいます。
でも、組み合わせ(Combination)を列挙する実装は、あまり書かれていないような気がする*1。
実際に自分で実装してみるとわかるが、自分のような脳のスペックが低いタイプの人間にとっては、
なかなかややこしくて面倒くさ〜い感じのアルゴリズムが要求され、とても頭が痛くなる。
しかも、パスカルの三角形ってどんなんだっけかなとか、高校数学の記憶すら怪しいのだから、もーねー。
以前、ロト6およびナンバーズ購入のための「俺専用数字選択方式くじ予想ソフト」とかゆー、
非常にしょっぱいアプリを作ったときに、順列や組み合わせを生成する必要に迫られました。
そのとき作ったしょっぱい2つのクラスを、少し修正して公開したいと思います。
見る人が見るとしょっぱい実装かもしれませんが、なかなか実用性はあると思います。
例えば、すべての組み合わせのテストケースを網羅したいなんて場合にも使えるでしょう。
では、どうぞ。
詳しいアルゴリズムについては、コードを読んでください。読めばきっとわかります。
順列(Permutation)
using System; using System.Collections.Generic; namespace ConsoleApplication1 { /// <summary> /// 順列 /// </summary> /// <typeparam name="T"></typeparam> public class Permutations<T> { #region メンバ private IList<T> _items; private int _length; private List<IList<T>> _permutations; private List<int[]> _indices; private int[] _value; private int _level = -1; #endregion #region コンストラクタ public Permutations(IList<T> items) : this(items, items.Count) { } public Permutations(IList<T> items, int select) { if (select < 0) throw new ArgumentException("選択要素数は、0以上でなくてはなりません。"); if (items.Count < select) throw new ArgumentException("選択要素数は、対象要素数以下でなくてはなりません。"); _items = items; _length = select; _permutations = new List<IList<T>>(); _indices = new List<int[]>(); if (select == 0) return; _value = new int[_length]; CreateCombinationIndices(0); foreach (var oneCom in new Combinations<T>(items, select)) _permutations.AddRange(GetPermutations(oneCom)); } #endregion #region プロパティ /// <summary> /// 順列の要素数を取得します。 /// </summary> public int Count { get { return _permutations.Count != 0 ? _permutations.Count : 1; } } #endregion #region メソッド /// <summary> /// 組み合わせに対する順列インデックスを生成 /// </summary> /// <param name="i"></param> private void CreateCombinationIndices(int i) { try { _value[i] = ++_level; if (_level != _length) { for (int j = 0; j < _length; j++) if (_value[j] == 0) CreateCombinationIndices(j); return; } int[] newValue = _value.Clone() as int[]; _indices.Add(newValue); } finally { _level--; _value[i] = 0; } } /// <summary> /// 順列を生成 /// </summary> /// <param name="oneCom"></param> /// <returns></returns> private IEnumerable<IList<T>> GetPermutations(IList<T> oneCom) { foreach (var idxs in _indices) { T[] onePerm = new T[_length]; for (int i = 0; i < _length; i++) { onePerm[i] = oneCom[idxs[i] - 1]; } yield return onePerm; } } /// <summary> /// 結果を返すイテレータ /// </summary> /// <returns></returns> public IEnumerator<IList<T>> GetEnumerator() { foreach (var item in _permutations) yield return item; } /// <summary> /// ToString /// </summary> /// <returns></returns> public override string ToString() { return string.Format("{0}P{1} Of [{2}] - {3}通り" , _items.Count , _length , Utility.GetString<T>(_items) , this.Count); } #endregion } }
組み合わせ(Combination)
using System; using System.Collections.Generic; using System.Linq; namespace ConsoleApplication1 { /// <summary> /// 組み合わせ /// </summary> /// <typeparam name="T"></typeparam> public class Combinations<T> { #region メンバ private IList<T> _items; private int _length; private List<IList<T>> _combinations; private int[] _finalIndices; #endregion #region コンストラクタ public Combinations(IList<T> items) : this(items, items.Count) { } public Combinations(IList<T> items, int select) { if (select < 0) throw new ArgumentException("選択要素数は、0以上でなくてはなりません。"); if (items.Count < select) throw new ArgumentException("選択要素数は、対象要素数以下でなくてはなりません。"); _items = items; _length = select; _combinations = new List<IList<T>>(); if (select == 0) return; _finalIndices = GetFinalIndices(select); ComputeCombination(); } #endregion /// <summary> /// 選択要素数に応じた組み合わせとなる最後の値を取得します。(終端の確定) /// </summary> /// <param name="select"></param> /// <returns></returns> private int[] GetFinalIndices(int select) { var finalindices = new int[select]; int j = select - 1; for (var i = _items.Count - 1; i > _items.Count - 1 - select; i--) { finalindices[j] = i; j--; } return finalindices; } #region プロパティ /// <summary> /// 組み合わせの要素数を取得します。 /// </summary> public int Count { get { return _combinations.Count != 0 ? _combinations.Count : 1; } } #endregion /// <summary> /// 条件をもとに組み合わせを求めます。 /// </summary> private void ComputeCombination() { if (_finalIndices.Length == 0) return; var indices = Enumerable.Range(0, _length).ToArray(); _combinations.Add(GetCurrentCombination(indices)); while (NextCombination(indices)) { _combinations.Add(GetCurrentCombination(indices)); } } /// <summary> /// 現在の組み合わせを取得します。 /// </summary> /// <param name="indices"></param> /// <returns></returns> private T[] GetCurrentCombination(int[] indices) { T[] oneCom = new T[_length]; for (var k = 0; k < _length; k++) { oneCom[k] = _items[indices[k]]; } return oneCom; } /// <summary> /// 次の組み合わせへ /// </summary> /// <param name="indices"></param> /// <returns></returns> private bool NextCombination(int[] indices) { for (var j = _finalIndices.Length - 1; j > -1; j--) { if (indices[j] < _finalIndices[j]) { indices[j]++; for (var k = 1; j + k < _finalIndices.Length; k++) { indices[j + k] = indices[j] + k; } break; } if (j == 0) return false; } return true; } /// <summary> /// イテレータ /// </summary> /// <returns></returns> public IEnumerator<IList<T>> GetEnumerator() { foreach (var item in _combinations) yield return item; } /// <summary> /// ToString /// </summary> /// <returns></returns> public override string ToString() { return string.Format("{0}C{1} Of [{2}] - {3}通り" , _items.Count , _length , Utility.GetString<T>(_items) , this.Count); } } }
ユーティリティ的な
using System.Collections.Generic; using System.Text; namespace ConsoleApplication1 { public static class Utility { /// <summary> /// IList(T)の要素を文字列化したものすべてを連結した文字列を取得します。 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="list"></param> /// <returns></returns> public static string GetString<T>(IList<T> list) { var sb = new StringBuilder(); foreach (T item in list) { sb.Append(item.ToString() + ","); } if (sb.Length > 0) sb.Remove(sb.Length - 1, 1); return sb.ToString(); } } }
お試しプログラム
using System; using System.Collections; using System.Collections.Generic; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { var a = new int[] { }; WriteCombinations<int>(a, 0); WritePermutations<int>(a, 0); Console.ReadLine(); var b = new string[] { "dog", "cat", "bird" }; WriteCombinations<string>(b, 0); WritePermutations<string>(b, 0); Console.ReadLine(); var c = new string[] { "dog", "cat", "bird", "snake" }; WriteCombinations<string>(c, 3); WritePermutations<string>(c, 2); Console.ReadLine(); //当然、匿名型だっていけちゃいますよ var 少年メリケンサック = new[] {new { Name = "宮藤官九郎" , Age = 38 } ,new { Name = "宮崎あおい" , Age = 23 } ,new { Name = "佐藤浩市" , Age = 48 } ,new { Name = "木村祐一" , Age = 45 } ,new { Name = "ユースケ・サンタマリア" , Age = 37 } ,new { Name = "ピエール瀧" , Age = 41 } ,new { Name = "哀川翔" , Age = 47 }}; WriteCombinations(少年メリケンサック, 2); WritePermutations(少年メリケンサック, 2); Console.ReadLine(); } static void WritePermutations<T>(T[] array, int length) { var permutations = new Permutations<T>(array, length); foreach (var perm in permutations) { Console.WriteLine(Utility.GetString<T>(perm)); } Console.WriteLine(permutations.ToString()); Console.WriteLine(); } static void WriteCombinations<T>(T[] array, int length) { var combinations = new Combinations<T>(array, length); foreach (var oneCom in combinations) { Console.WriteLine(Utility.GetString<T>(oneCom)); } Console.WriteLine(combinations.ToString()); Console.WriteLine(); } } }
実行結果
0C0 Of [] - 1通り 0P0 Of [] - 1通り 3C0 Of [dog,cat,bird] - 1通り 3P0 Of [dog,cat,bird] - 1通り dog,cat,bird dog,cat,snake dog,bird,snake cat,bird,snake 4C3 Of [dog,cat,bird,snake] - 4通り dog,cat cat,dog dog,bird bird,dog dog,snake snake,dog cat,bird bird,cat cat,snake snake,cat bird,snake snake,bird 4P2 Of [dog,cat,bird,snake] - 12通り { Name = 宮藤官九郎, Age = 38 },{ Name = 宮崎あおい, Age = 23 } { Name = 宮藤官九郎, Age = 38 },{ Name = 佐藤浩市, Age = 48 } { Name = 宮藤官九郎, Age = 38 },{ Name = 木村祐一, Age = 45 } { Name = 宮藤官九郎, Age = 38 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = 宮藤官九郎, Age = 38 },{ Name = ピエール瀧, Age = 41 } { Name = 宮藤官九郎, Age = 38 },{ Name = 哀川翔, Age = 47 } { Name = 宮崎あおい, Age = 23 },{ Name = 佐藤浩市, Age = 48 } { Name = 宮崎あおい, Age = 23 },{ Name = 木村祐一, Age = 45 } { Name = 宮崎あおい, Age = 23 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = 宮崎あおい, Age = 23 },{ Name = ピエール瀧, Age = 41 } { Name = 宮崎あおい, Age = 23 },{ Name = 哀川翔, Age = 47 } { Name = 佐藤浩市, Age = 48 },{ Name = 木村祐一, Age = 45 } { Name = 佐藤浩市, Age = 48 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = 佐藤浩市, Age = 48 },{ Name = ピエール瀧, Age = 41 } { Name = 佐藤浩市, Age = 48 },{ Name = 哀川翔, Age = 47 } { Name = 木村祐一, Age = 45 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = 木村祐一, Age = 45 },{ Name = ピエール瀧, Age = 41 } { Name = 木村祐一, Age = 45 },{ Name = 哀川翔, Age = 47 } { Name = ユースケ・サンタマリア, Age = 37 },{ Name = ピエール瀧, Age = 41 } { Name = ユースケ・サンタマリア, Age = 37 },{ Name = 哀川翔, Age = 47 } { Name = ピエール瀧, Age = 41 },{ Name = 哀川翔, Age = 47 } 7C2 Of [{ Name = 宮藤官九郎, Age = 38 },{ Name = 宮崎あおい, Age = 23 },{ Name = 佐藤浩市, Age = 48 },{ Name = 木村祐一, Age = 45 },{ Name = ユースケ・サンタマ リア, Age = 37 },{ Name = ピエール瀧, Age = 41 },{ Name = 哀川翔, Age = 47 }] - 21通り { Name = 宮藤官九郎, Age = 38 },{ Name = 宮崎あおい, Age = 23 } { Name = 宮崎あおい, Age = 23 },{ Name = 宮藤官九郎, Age = 38 } { Name = 宮藤官九郎, Age = 38 },{ Name = 佐藤浩市, Age = 48 } { Name = 佐藤浩市, Age = 48 },{ Name = 宮藤官九郎, Age = 38 } { Name = 宮藤官九郎, Age = 38 },{ Name = 木村祐一, Age = 45 } { Name = 木村祐一, Age = 45 },{ Name = 宮藤官九郎, Age = 38 } { Name = 宮藤官九郎, Age = 38 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = ユースケ・サンタマリア, Age = 37 },{ Name = 宮藤官九郎, Age = 38 } { Name = 宮藤官九郎, Age = 38 },{ Name = ピエール瀧, Age = 41 } { Name = ピエール瀧, Age = 41 },{ Name = 宮藤官九郎, Age = 38 } { Name = 宮藤官九郎, Age = 38 },{ Name = 哀川翔, Age = 47 } { Name = 哀川翔, Age = 47 },{ Name = 宮藤官九郎, Age = 38 } { Name = 宮崎あおい, Age = 23 },{ Name = 佐藤浩市, Age = 48 } { Name = 佐藤浩市, Age = 48 },{ Name = 宮崎あおい, Age = 23 } { Name = 宮崎あおい, Age = 23 },{ Name = 木村祐一, Age = 45 } { Name = 木村祐一, Age = 45 },{ Name = 宮崎あおい, Age = 23 } { Name = 宮崎あおい, Age = 23 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = ユースケ・サンタマリア, Age = 37 },{ Name = 宮崎あおい, Age = 23 } { Name = 宮崎あおい, Age = 23 },{ Name = ピエール瀧, Age = 41 } { Name = ピエール瀧, Age = 41 },{ Name = 宮崎あおい, Age = 23 } { Name = 宮崎あおい, Age = 23 },{ Name = 哀川翔, Age = 47 } { Name = 哀川翔, Age = 47 },{ Name = 宮崎あおい, Age = 23 } { Name = 佐藤浩市, Age = 48 },{ Name = 木村祐一, Age = 45 } { Name = 木村祐一, Age = 45 },{ Name = 佐藤浩市, Age = 48 } { Name = 佐藤浩市, Age = 48 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = ユースケ・サンタマリア, Age = 37 },{ Name = 佐藤浩市, Age = 48 } { Name = 佐藤浩市, Age = 48 },{ Name = ピエール瀧, Age = 41 } { Name = ピエール瀧, Age = 41 },{ Name = 佐藤浩市, Age = 48 } { Name = 佐藤浩市, Age = 48 },{ Name = 哀川翔, Age = 47 } { Name = 哀川翔, Age = 47 },{ Name = 佐藤浩市, Age = 48 } { Name = 木村祐一, Age = 45 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = ユースケ・サンタマリア, Age = 37 },{ Name = 木村祐一, Age = 45 } { Name = 木村祐一, Age = 45 },{ Name = ピエール瀧, Age = 41 } { Name = ピエール瀧, Age = 41 },{ Name = 木村祐一, Age = 45 } { Name = 木村祐一, Age = 45 },{ Name = 哀川翔, Age = 47 } { Name = 哀川翔, Age = 47 },{ Name = 木村祐一, Age = 45 } { Name = ユースケ・サンタマリア, Age = 37 },{ Name = ピエール瀧, Age = 41 } { Name = ピエール瀧, Age = 41 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = ユースケ・サンタマリア, Age = 37 },{ Name = 哀川翔, Age = 47 } { Name = 哀川翔, Age = 47 },{ Name = ユースケ・サンタマリア, Age = 37 } { Name = ピエール瀧, Age = 41 },{ Name = 哀川翔, Age = 47 } { Name = 哀川翔, Age = 47 },{ Name = ピエール瀧, Age = 41 } 7P2 Of [{ Name = 宮藤官九郎, Age = 38 },{ Name = 宮崎あおい, Age = 23 },{ Name = 佐藤浩市, Age = 48 },{ Name = 木村祐一, Age = 45 },{ Name = ユースケ・サンタマ リア, Age = 37 },{ Name = ピエール瀧, Age = 41 },{ Name = 哀川翔, Age = 47 }] - 42通り
てな具合です。なかなかいい感じですね。
このような実装を見ると、ジェネリックが使えない頃が不憫に思えてなりませんw
もう.NET Framework1.x時代には決して戻りたくありません。2.0でさえ厳しいと最近は思いますね。
この実装が何かのお役に立てれば幸いです。それはそうと、少年メリケンサック、はやく観たいのです。
*1:「ネット上で」という話です