LINQで選択肢の全組み合わせ展開

10994 ワード
再帰 C# LINQ C# テキストリンク

選択肢を与えて、重複のない全組み合わせを返す

1,2,3の選択肢がある時に、{1,2,3}{1,3,2}{2,1,3}{2,3,1}{3,1,2}{3,2,1}のように重複のない全組み合わせを書く必要があったのでやってみた。
使う時にお手軽にしたいので、拡張メソッドとして作る。

Extention.cs
        /// <summary>
        /// 選択肢の列挙の全組み合わせを展開
        /// choices {1,2,3}⇒ 戻り値{1,2,3}{1,3,2}{2,1,3}{2,3,1}{3,1,2}{3,2,1}
        /// </summary>
        /// <typeparam name="T">型引数</typeparam>
        /// <param name="choices">選択肢の列挙</param>
        /// <returns>展開結果</returns>
        public static IEnumerable<T[]> Expand<T>(this IEnumerable<T> choices)
        {
            //重複あり
            if (choices.Count() != choices.Distinct().Count()) { throw new Exception("has duplicate value"); }

            //選択結果は空からスタート
            var choosed = new T[] { };

            //展開開始
            var query = Expand(choices, choosed);
            return query;
        }

        /// <summary>
        /// 選択肢の列挙の全組み合わせを展開(再帰)
        /// </summary>
        /// <typeparam name="T">型引数</typeparam>
        /// <param name="choices">選択肢の列挙</param>
        /// <param name="choosed">選択済要素の列挙</param>
        /// <returns></returns>
        private static IEnumerable<T[]> Expand<T>(IEnumerable<T> choices, IEnumerable<T> choosed)
        {
            //選択肢がなくなったら終了
            if (!choices.Any()) { yield return choosed.ToArray(); }

            foreach (var choice in choices)
            {
                //選択肢から1つ選んで、選択済要素に入れる
                var newChoosed = choosed.Concat(new T[] { choice });

                //選択肢から削除
                var newChoices = choices.Where(v => !choice.Equals(v));

                //新たな選択肢と選択済要素で再帰
                var query = Expand(newChoices, newChoosed);
                foreach (var qq in query)
                {
                    //配列を順次返す
                    yield return qq.ToArray();
                }
            }
        }

        /// <summary>
        /// 結果表示用
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="query"></param>
        public static void DisplayElement<T>(this IEnumerable<T[]> query)
        {
            foreach (var q in query)
            {
                Console.WriteLine(string.Join(" ", q));
            }
        }

実行してみる

実行用のドライバ書いて。。。

Program.cs
        public static void Main(string[] args)
        {
            var items = new int[] { 1, 2, 3 };

            var query = items.Expand<int>();
            query.DisplayElement<int>();
        }

実行！想定通り。

要素を4つに増やしてみる。

Program.cs
        public static void Main(string[] args)
        {
            var items = new int[] { 1, 2, 3, 4 };

            var query = items.Expand<int>();
            query.DisplayElement<int>();
        }

おっけー。