場合の数

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Test
{
    class Program
    {
        static void Main(string[] args)
        {
            foreach (var item in Combination(new string[] { "A", "B", "C", "D" }, 2))
            {
                Console.WriteLine(string.Join(", ", item));
            }
            Console.WriteLine();

            foreach (var item in Combination(new string[] { "A", "B", "C", "D" }, 4))
            {
                Console.WriteLine(string.Join(", ", item));
            }
            Console.WriteLine();

            foreach (var item in Permutation(new string[] { "A", "B", "C", "D" }, 2))
            {
                Console.WriteLine(string.Join(", ", item));
            }
            Console.WriteLine();

            foreach (var item in Permutation(new string[] { "A", "B", "C" }))
            {
                Console.WriteLine(string.Join(", ", item));
            }
            Console.ReadKey();
        }

        /*
        static IEnumerable<IEnumerable<T>> Permutation<T>(IEnumerable<T> source)
        {
            // 要素が一つだけならそのまま返す
            if (source.Count() > 1 == false) return new List<IEnumerable<T>>() { source };

            // 結果を格納するList
            var result = new List<List<T>>();
            // 先頭に1要素ずつ置く
            foreach (var item in source)
            {
                // 先頭以外の要素で組み合わせを求める
                foreach (var inner in Combination(source.TakeWhile(p => !p.Equals(item)).Concat(source.SkipWhile(p => !p.Equals(item)).Skip(1))))
                {
                    // 1つの組み合わせを表すList
                    var each = new List<T>();
                    // 先頭の要素を入れる
                    each.Add(item);
                    // 後続の組み合わせをそのまま入れる
                    foreach (T inneritem in inner) each.Add(inneritem);
                    // 組み合わせ1つ出来上がり
                    result.Add(each);
                }
            }
            return result;
        }
        */
        static IEnumerable<IEnumerable<T>> Permutation<T>(IEnumerable<T> source)
        {
            return Permutation(source, source.Count());
        }

        /// <summary>
        /// 順列を求める
        /// </summary>
        static IEnumerable<IEnumerable<T>> Permutation<T>(IEnumerable<T> source, int count)
        {
            // パラメータチェック
            if (source.Count() < count || count < 0) throw new ArgumentOutOfRangeException("count", "取り出す個数が不正です。");
            // 要素が一つだけならそのまま返す
            if (source.Count() > 1 == false) return new List<IEnumerable<T>>() { source };

            // 結果を格納するList
            var result = new List<List<T>>();
            // 先頭に1要素ずつ置く
            foreach (var item in source)
            {
                // 最後の要素だったら返す
                if (count > 1 == false)
                {
                    result.Add(new List<T>() { item });
                    continue;
                }
                // 先頭以外の要素で組み合わせを求める
                foreach (var inner in Permutation(source.TakeWhile(p => !p.Equals(item)).Concat(source.SkipWhile(p => !p.Equals(item)).Skip(1)), count - 1))
                {
                    // 1つの組み合わせを表すList
                    var each = new List<T>();
                    // 先頭の要素を入れる
                    each.Add(item);
                    // 後続の組み合わせをそのまま入れる
                    foreach (T inneritem in inner) each.Add(inneritem);
                    // 組み合わせ1つ出来上がり
                    result.Add(each);
                }
            }
            return result;
        }

        /// <summary>
        /// 組み合わせを求める
        /// </summary>
        static IEnumerable<IEnumerable<T>> Combination<T>(IEnumerable<T> source, int count)
        {
            // 典型的な場当たりコーディング

            // パラメータチェック
            if (source.Count() < count || count < 0) throw new ArgumentOutOfRangeException("count", "取り出す個数が不正です。");
            // 要素が一つだけならそのまま返す
            if (source.Count() > 1 == false) return new List<IEnumerable<T>>() { source };

            // 結果を格納するList
            var result = new List<List<T>>();
            // 残りの組み合わせに使うリスト
            var remain = new List<T>(source);
            // 先頭に1要素ずつ置く
            foreach (var item in source)
            {
                // 最後の要素だったら飛ばす
                if (count > 1 == false)
                {
                    result.Add(new List<T>() { item });
                    continue;
                }
                remain.Remove(item);
                // 組み合わせる要素がなくなったら終わり
                if (remain.Count > 0 == false || remain.Count < count - 1) break; // ←特にこ↑こ↓
                // 先頭以外の要素で組み合わせを求める
                foreach (var inner in Combination(remain, count - 1))
                {
                    // 1つの組み合わせを表すList
                    var each = new List<T>();
                    // 先頭の要素を入れる
                    each.Add(item);
                    // 後続の組み合わせをそのまま入れる
                    foreach (T inneritem in inner) each.Add(inneritem);
                    // 組み合わせ1つ出来上がり
                    result.Add(each);
                }

            }
            return result;
        }

    }
}