可変個の集合から、直積の集合を作る
集合の個数が固定ならば、[C#]forever for(のコメント欄)のようにすれば簡単だけど、可変個の場合ちょっとややこしいなぁーとか思いつつググってたら、こんなん見つけた。
id:youkoso_guest:20081212:1229089595
reduceってなんぞ?ってな感じだったので、さらにググってみたらSchemeのfoldじゃあーりませんか。
ってことで、これをC#でやってみた。(っていうか単なる翻訳だけど)
// 直積の集合を列挙 static public IEnumerable<IEnumerable<T>> EnumerateDirectProduct<T>(IEnumerable<IEnumerable<T>> sets) { return sets.Fold( (list, prod) => from x in prod from y in list select x.Concat(Enumerable.Repeat(y, 1)), Enumerable.Repeat(Enumerable.Empty<T>(), 1)); } // reduce的なもの static public IEnumerable<T> Fold<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>, IEnumerable<T>> proc, IEnumerable<T> init) { return !source.GetEnumerator().MoveNext() ? init : source.Skip(1).Fold(proc, proc(source.ElementAt(0), init)); }
LINQはリスト内包表記なんだな。しかし読みにくい...。否!澄んだ心で見れば大丈夫。
Foldもひどい。効率とかいろいろ無視で無理矢理再帰。完全にSchemeに毒されております。イテレータ生成しないとコレクションが空かどうか判断できないのかなぁ。Schemeのnull?に相当することがもっと簡単にできればいいのにな。
で、EnumerateDirectProductを使ってみると
// sets は {{1,2}, {3,4}, {5,6}} IEnumerable<IEnumerable<int>> sets = new List<IEnumerable<int>> { Enumerable.Range(1, 2), Enumerable.Range(3, 2), Enumerable.Range(5, 2) }; // result は // {{1,3,5} // {1,3,6} // {1,4,5} // {1,4,6} // {2,3,5} // {2,3,6} // {2,4,5} // {2,4,6}} var result = EnumerateDirectProduct(sets);
型関連でややこしく感じるのは、静的型のせいなのか、自分のスキルが不足なのか。特にFold内のproc。
あと、可変個の集合の要素の静的型は全て同じじゃないとだめ。例えば、上で挙げたブログのように、IEnumerable