ようこそ。睡眠不足なプログラマのチラ裏です。
トップ > アルゴリズム

C#で順列(Permutation)と組み合わせ(Combination)をすべて列挙してみよう

アルゴリズム C#2.0 C#3.0


さて、いきなり少年メリケンサックですが、気にしないでください。帰らないでください。内容はまともです。


C#で順列(Permutation)を列挙する実装については、割と書いている人がいます。
でも、組み合わせ(Combination)を列挙する実装は、あまり書かれていないような気がする*1。
実際に自分で実装してみるとわかるが、自分のような脳のスペックが低いタイプの人間にとっては、
なかなかややこしくて面倒くさ〜い感じのアルゴリズムが要求され、とても頭が痛くなる。
しかも、パスカルの三角形ってどんなんだっけかなとか、高校数学の記憶すら怪しいのだから、もーねー。


以前、ロト６およびナンバーズ購入のための「俺専用数字選択方式くじ予想ソフト」とかゆー、
非常にしょっぱいアプリを作ったときに、順列や組み合わせを生成する必要に迫られました。
そのとき作ったしょっぱい２つのクラスを、少し修正して公開したいと思います。
見る人が見るとしょっぱい実装かもしれませんが、なかなか実用性はあると思います。
例えば、すべての組み合わせのテストケースを網羅したいなんて場合にも使えるでしょう。


では、どうぞ。
詳しいアルゴリズムについては、コードを読んでください。読めばきっとわかります。


順列(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通り

てな具合です。なかなかいい感じですね。


このような実装を見ると、ジェネリックが使えない頃が不憫に思えてなりませんｗ
もう.NET Framework1.x時代には決して戻りたくありません。2.0でさえ厳しいと最近は思いますね。
この実装が何かのお役に立てれば幸いです。それはそうと、少年メリケンサック、はやく観たいのです。

*1:「ネット上で」という話です

モテようとして、C#でXOR使ってリバースしている奴がいたんですよ

アルゴリズム C# C#2.0 C#3.0

いろいろなリバースのアルゴリズムを見てみましよう。
まずは表題のリバースのアルゴリズムについて、どうぞ。

なんとなくモテようとしている感のあるリバース

モテようとして、C#でXOR使ってリバースしている奴がいたんですよ・・(以下略)。


こんな感じで

        public static string Reverse(string s)
        {
            char[] charArray = s.ToCharArray();
            int len = s.Length - 1;
            for (int i = 0; i < len; i++, len--)
            {
                charArray[i] ^= charArray[len];
                charArray[len] ^= charArray[i];
                charArray[i] ^= charArray[len];
            }
            return new string(charArray);
        }

もちろん要件は満たしているし、それほど遅いアルゴリズムでもないので、
私的にはギリギリセーフなんですが、なんとなくやっちまってる感が・・ね。
どうも無理にXOR使ってスワップをして「モテ」を意識しているようです。
嫌いじゃないですがちょっとキモイです(笑)



新人くんにありがちなリバース

        public static string Reverse(string s)
        {
            return new string(s.ToCharArray().Reverse().ToArray());
        }

完全にやっちまってますね。イテリセンス利きまくりのIDEに飼いならされた新人が
「.」押して出てきたやつを次々につなげたらリバースできちゃったよー的な。
これは、超おそおそアルゴなので論外です。新人じゃない場合は・・・＼(^o^)／


VB.NET厨寄りC#erにありがちなリバース

        public static string Reverse(string s)
        {
            return Microsoft.VisualBasic.Strings.StrReverse(s);
        }

StrReverseキタコレ。まぁ、間違ってはいないんだけどね・・。
「車輪の再発明はしない的理論だよ」というのであれば、そのまま使え、と。
ちったあ、頭つかいましょうよ、と思っちゃいますね。



一般的によく書かれてそうなリバース

        public static string Reverse(string s)
        {
            char[] charArray = new char[s.Length];
            int len = s.Length - 1;
            for (int i = 0; i <= len; i++)
                charArray[i] = s[len - i];
            return new string(charArray);
        }

ノーマルなC#erが最も書きそうな感じです。
教科書通り的な雰囲気があります。特に文句はありません。
書けといわれたら、自分もたぶんこれ書きます。


別によいんだけど、なんとなく残念なリバース

        public static string Reverse(string s)
        {
            char[] arr = s.ToCharArray();
            Array.Reverse(arr);
            return new string(arr);
        }

ノーマルなC#erが割と書きそうな感じです。
確かに、その発想もあるよね。悪くは無いです。あると思います。
そうも思うんだけど、なんとなく賛同できない俺ガイル。


StringBuilderに洗脳されている残念な人のリバース

        public static string Reverse(string s)
        {
            char[] cArray = s.ToCharArray();
            StringBuilder reverse = new StringBuilder();
            for (int i = cArray.Length - 1; i > -1; i--)
            {
                reverse.Append(cArray[i]);
            }
            return reverse.ToString();
        }

間違ってはいないんだけど、StringBuilder使えばいいっちゅーもんでもない。
とりあえず、洗脳を解いてあげたい。


人とは毛色が違いますね・・。正直やめて欲しい個性的なリバース

        public static string Reverse(string s)
        {
            Stack<string> stack = new Stack<string>();
            for (int i = 0; i < s.Length; i++)
                stack.Push(s.Substring(i, 1));
            string ns = string.Empty;
            for (int i = 0; i < s.Length; i++)
                ns += stack.Pop();
            return ns;
        }

これはひどい低速アルゴですね。
スタック使っちゃいますか。そうですか、わかりません。
基本的なところから再教育が必要かもしれません。


がんばったと決して褒めたくない再帰的なリバース

　      public static string Reverse(string s, int length)
        {
            if (length == 1) return s;
            return Reverse(s.Substring(1, s.Length - 1), --length) + s[0].ToString();
        }

これもひどい低速アルゴです。ダサいです。
思考的ベクトルの方向が全くわかりません。本当にありがとうございました。


にわか仕込みラムダ厨による超低速リバース

        public static string Reverse(string s)
        {
            Func<string, string> f = null;
            f = x => x.Length > 0 ? f(x.Substring(1)) + x[0] :
                     string.Empty;
            return f(s);
        }

ラムダで書きゃーいいってもんじゃないです。
見なかったことにしてあげるので、今すぐ書き直してください。
できれば死なない程度に死んでください(^-^)


様々なリバースを見てきましたが、まだ飽き足らないあなたへ

unsafeでポインタつかって無駄に高速化をはかります。
ポインタ使うと速くなるのは、配列のバインド チェックが削除されるからです。


まずは普通に書く。(これが一番高速っぽいです)

        unsafe static string Reverse(string s)
        {
            fixed (char* pc = s)
            {
                string newtext = new string(pc);
                fixed (char* pChar = newtext)
                {
                    char swapChar;
                    int length = s.Length - 1;
                    for (int i = 0, j = length; i < j; i++, j--)
                    {
                        swapChar = pChar[i];
                        pChar[i] = pChar[j];
                        pChar[j] = swapChar;
                    }
                }
                return newtext;
            }
        }


せっかくだから、俺はポインタでスワップするゼ

        unsafe static string Reverse(string s)
        {
            fixed (char* pc = s)
            {
                string newtext = new string(pc);
                fixed (char* pChar = newtext)
                {
                    char swapChar;
                    int length = s.Length - 1;
                    char* pStart = pChar;
                    char* pEnd = pChar + length;

                    while (pStart < pEnd)
                    {
                        swapChar = *pStart;
                        *pStart = *pEnd;
                        *pEnd = swapChar;

                        pStart++;
                        pEnd--;
                    }
                } 
                return newtext;
            }
        }


unsafeでもやっぱりXORでモテたい人のリバース

        unsafe static string Reverse(string s)
        {
            fixed (char* pc = s)
            {
                string newtext = new string(pc);
                fixed (char* pChar = newtext)
                {
                    int length = s.Length - 1;
                    for (int i = 0, j = length; i < j; i++, j--)
                    {
                        pChar[i] ^= pChar[j];
                        pChar[j] ^= pChar[i];
                        pChar[i] ^= pChar[j];
                    }
                } 
                return newtext;
            }
        }


「ワシのリバースは108式まであるぞ！」
という方がいらっしゃいましたら、ぜひ教えて頂ければ幸いです。
関係ないけど、ラムダ式の中でもunsafeって書けるんですね。今日初めて書きました。

IEnumerableをシャッフル！

プログラミング アルゴリズム C#3.0

ネタ元：id:kawatanさんのエントリより
http://d.hatena.ne.jp/kawatan/20081210


IEnumerableを実装していれば何でもシャッフルって、素敵ですね〜。
カードゲームなんか作るときにサクッと利用できちゃいますね。
よいものは盗んじゃおう！ということで、さっそく自分専用俺俺フレームワークに拡張メソッドを追加しました。
あ、Fisher-Yatesアルゴリズムみたいなアルゴリズムって、ラスベガス法とかなんとか言うんですよね確か。


あと、重箱の隅をつつくようで大変恐縮なんですが・・、
Listをnewするよりも、ToArray()メソッドを利用した方が若干早いのかなと思いました*1。
加えて、yield returnするようにしてみたり、無駄にクロージャで覆い被せてディレイしてみました。
yieldキーワードはラムダ式の中に直接記述できませんが、イテレータブロックはラムダ式内に記述可能なので、
yield returnしているイテレータブロックをラムダ式内に記述することで、
実質的にyield returnをラムダ式内に書いているかのような振る舞いを表現することができますね。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication1
{
    public static class IEnumerableExtentions
    {
        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> self)
        {
            // Fisher-Yates
            var r = new Random(DateTime.Now.Millisecond);
            var array = self.ToArray();

            int i = self.Count();
            while (i > 1)
            {
                int j = r.Next(i--);
                T temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
            foreach (var item in array) yield return item;
        }

        public static Func<IEnumerable<T>> DelayShuffle<T>(this IEnumerable<T> self)
        {
            return () => { return self.Shuffle() ; }; 
        }
    }

    public class Program
    {
        private static void Main()
        {
            var numberList = Enumerable.Range(0, 10000);

            var sw = new Stopwatch();
            for (var i = 1; i <= 10; i++)
            {
                Console.WriteLine("---{0}回目---", i);
                sw.Reset();
                sw.Start();
                numberList.Shuffle();
                sw.Stop();
                Console.WriteLine("(1):{0}", sw.Elapsed);

                sw.Reset();
                sw.Start();
                numberList.DelayShuffle();
                sw.Stop();
                Console.WriteLine("(2):{0}", sw.Elapsed);
            }
            Console.ReadLine();
        }
    }
}

シャッフル結果はあえて出力していません(・ω・)


DelayShuffleの方がクロージャにしてある分、評価が若干早いっぽいです。
でも、偶にDelayShuffleの方が遅いこともあったり早いこともあったりラジバンダリ・・。
もしかすると、このDelayShuffleは意味ないかも・・。意味なかったらごめんなさい(笑)

*1:目くそ鼻くそ程度の差ですが・・。

いまさらC#でライフゲームを書いてみた

プログラミング アルゴリズム C#3.0


どう書く？orgにて、C#で既に書いてらっしゃる方が多数おられますが、
どうもコードを短くすることに重点を置いて書いているような感じで、正直なんだか読みにくいなーと思い・・・。
冗長だけどわかりやすく、オブジェクト指向っぽくライフゲームを書いてみることにしました*1。


※ライフゲームについての説明は、ライフゲーム - Wikipediaを参照ください。


Cellクラス

まず、細胞ひとつひとつを表すCellクラスを作ることにします。
IsAliveによって、細胞が生きているかどうかがわかるようにします。

using System;

namespace LifeGameLibrary
{
    /// <summary>
    /// 細胞クラス
    /// </summary>
    [Serializable]
    public class Cell  
    {
        /// <summary>
        /// コンストラクタ
        /// </summary>
        public Cell() {
            this.Age = 0;
        }

        /// <summary>
        /// コンストラクタ
        /// </summary>
        public Cell(bool alive)
        {
            this.Age = 0;
            this.IsAlive = alive;
        }

        /// <summary>
        /// 生死
        /// </summary>
        public bool IsAlive { get; set; }

        /// <summary>
        /// 細胞年齢
        /// </summary>
        public long Age { get; set; }
    }
}

CellMapクラス

続きまして、細胞ひとつひとつの座標位置を表すマップを作ります。
まぁいろいろやってます、コードを読んでください。

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

namespace LifeGameLibrary
{
    /// <summary>
    /// 細胞マップ
    /// </summary>
    [Serializable]
    public class CellMap : ICloneable 
    {
        private Cell[,] map;
       
        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="width">マップの幅</param>
        /// <param name="height">マップの高さ</param>
        public CellMap(int width, int height)
        {
            // 世代を初期化
            this.Generation = 0;

            this.map = new Cell[width, height];
            for (int x = 0; x < width; x++)
            {
                for (int y = 0; y < height; y++)
                {
                    this.map[x, y] = new Cell();
                }
            }
        }

        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="mapString">マップ文字列</param>
        public CellMap(IEnumerable<string> mapString,char alive) {
            var mapInfo = from map in mapString
                          where map.Length == mapString.Max(x => x.Length)
                          let count = mapString.Count()
                          select new { column = mapString.Max(x => x.Length), row = count };

            foreach (var t in mapInfo)
            {
                this.map = new Cell[t.column, t.row];
                this.ColumnCount = t.column;
                this.RowCount = t.row; 

                var r = -1;
                foreach (var row in mapString) 
                {
                    r++;
                    //改行で分割して文字配列にしてセット
                    var record = row.ToCharArray();
                    for (int x = 0; x < t.column; x++)
                    {
                        this.map[x, r] = new Cell(record[x] == alive);
                    }
                }
            }
        }

        /// <summary>
        /// 列数
        /// </summary>
        public int ColumnCount { get; set; }

        /// <summary>
        /// 行数
        /// </summary>
        public int RowCount { get; set; }

        /// <summary>
        /// 指定した座標位置の細胞
        /// </summary>
        /// <param name="x">x座標</param>
        /// <param name="y">y座標</param>
        /// <returns>細胞</returns>
        public Cell this[int x, int y]
        {
            get { return this.map[x, y]; }
            set { this.map[x, y] = value; }
        }

        /// <summary>
        /// マップの幅
        /// </summary>
        public int Width
        {
            get { return this.map.GetLength(0); }
        }

        /// <summary>
        /// マップの高さ
        /// </summary>
        public int Height
        {
            get { return this.map.GetLength(1); }
        }

        /// <summary>
        /// マップの世代
        /// </summary>
        public long Generation { get; set; }

        /// <summary>
        /// 細胞マップを文字列で取得します。
        /// </summary>
        /// <param name="alive">生存を表す文字</param>
        /// <param name="dead">死亡を表す文字</param>
        /// <returns></returns>
        public string GetCellMapString(char alive,char dead)
        {
            var sb = new StringBuilder();
            for (int y = 0; y < this.RowCount; y++)
            {
                for (int x = 0; x < this.ColumnCount; x++){
                    sb.Append(this.map[x, y].IsAlive ? alive : dead );                
                }
                sb.Append((this.RowCount - 1 == y) ? "" : "\r\n");
            }
            return sb.ToString();
        }

        /// <summary>
        /// ディープコピークローンを取得します。
        /// </summary>
        /// <returns></returns>
        public CellMap DeepCopyClone()
        {
            return (CellMap)this.Clone();
        }

        #region ICloneable メンバ

        public object Clone()
        {
            return Serialization.DeepCopyClone<CellMap>(this);
        }

        #endregion
    }
}

ILivingConditionインターフェイス

続きまして、細胞の生存条件を表すインターフェイスを定義します。

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

namespace LifeGameLibrary
{
    /// <summary>
    /// 生存条件インターフェイス
    /// </summary>
    public interface ILivingCondition
    {
        /// <summary>
        /// 細胞マップの各細胞について、次世代の生存確認を行います。
        /// </summary>
        /// <param name="cellMap"></param>
        void ConfirmationAlive(CellMap cellMap);

        /// <summary>
        /// 隣接する細胞たちを取得します。
        /// </summary>
        /// <param name="cellMap">細胞マップ</param>
        /// <param name="x">X座標</param>
        /// <param name="y">Y座標</param>
        /// <returns>隣接する細胞たち</returns>
        IEnumerable<Cell> GetNeighbors(CellMap cellMap, int x, int y);
    }
}


AbstractLivingConditionクラス

先ほど作成したILivingConditionインターフェイスを実装した、
生存条件抽象クラスを作成します。コードのとおりです。

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

namespace LifeGameLibrary
{
    /// <summary>
    /// 生存条件抽象クラス
    /// </summary>
    public abstract class AbstractLivingCondition : ILivingCondition
    {
        /// <summary>
        /// 対象の細胞のうち、生存している細胞の数を取得します。
        /// </summary>
        /// <param name="cells">対象細胞</param>
        /// <returns>生きている細胞の数</returns>
        public virtual int GetNumberOfCellsToBeAlive(IEnumerable<Cell> cells)
        {
            int count = 0;
            foreach (Cell cell in cells)
            {
                if (cell.IsAlive)
                {
                    count++;
                }
            }
            return count;
        }

        #region ILivingCondition メンバ

        /// <summary>
        /// 次の世代の生存確認を行います。
        /// </summary>
        /// <param name="cellMap"></param>
        public abstract void ConfirmationAlive(CellMap cellMap);

        /// <summary>
        /// 隣接する細胞のイテレータを提供
        /// </summary>
        /// <param name="cellMap">細胞マップ</param>
        /// <param name="x">x座標</param>
        /// <param name="y">y座標</param>
        /// <returns>隣接する細胞</returns>
        public virtual IEnumerable<Cell> GetNeighbors(CellMap cellMap, int x, int y)
        {
            int w = cellMap.Width;
            int h = cellMap.Height;
            foreach (int xn in new int[] { x - 1, x + 1, x })
            {
                foreach (int yn in new int[] { y - 1, y + 1, y })
                {
                    if ((xn != x) || (yn != y))
                    {
                        if ((xn >= 0) && (xn < w) && (yn >= 0) && (yn < h))
                        {
                            yield return cellMap[xn, yn];
                        }
                    }
                }
            }
            yield break;
        }
        #endregion
    }
}


StandardLivingConditionクラス

生存条件抽象クラスから派生し、ライフゲームの標準的な生存条件クラスを作成します。
ここで初めて、ConfirmationAliveメソッドが実装されています。

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

namespace LifeGameLibrary
{
    /// <summary>
    /// ライフゲームの標準的な生存条件
    /// </summary>
    public class StandardLivingCondition : AbstractLivingCondition
    {
        private IEnumerable<int> NumberOfNeighborsToAlive{get;set;}
        private IEnumerable<int> NumberOfNeighborsToBeBorn{get;set;}

        /// <summary>
        /// 条件：23/3
        /// </summary>
        public static readonly StandardLivingCondition Original = new StandardLivingCondition(new int[] { 2, 3 }, new int[] { 3 });

        /// <summary>
        /// 条件：23/36
        /// </summary>
        public static readonly StandardLivingCondition HighLife = new StandardLivingCondition(new int[] { 2, 3 }, new int[] { 3, 6 });

        #region コンストラクタ
        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="numberOfNeighborsToAlive"></param>
        /// <param name="numberOfNeighborsToBeBorn"></param>
        public StandardLivingCondition(IEnumerable<int> numberOfNeighborsToAlive, IEnumerable<int> numberOfNeighborsToBeBorn)
        {
            this.NumberOfNeighborsToAlive = from num in numberOfNeighborsToAlive
                                            orderby num
                                            select num;
            this.NumberOfNeighborsToBeBorn = from num in numberOfNeighborsToBeBorn
                                             orderby num
                                             select num;
		}

        #endregion

        /// <summary>
        /// 細胞マップの各細胞について、次世代の生存確認を行います。
        /// </summary>
        /// <param name="cellMap">細胞マップ</param>
        public override void ConfirmationAlive(CellMap cellMap)
        {
            var oldCellMap = cellMap.DeepCopyClone();

            for (int x = 0; x < cellMap.Width; x++)
            {
                for (int y = 0; y < cellMap.Height; y++)
                {
                    var oldCell = oldCellMap[x, y];
                    var newCell = cellMap[x, y];
                    var neighbours = this.GetNeighbors(oldCellMap, x, y);
                    int aliveNeighborsCount = this.GetNumberOfCellsToBeAlive(neighbours);

                    if (oldCell.IsAlive)
                    {
                        newCell.IsAlive = Array.BinarySearch(this.NumberOfNeighborsToAlive.ToArray(), aliveNeighborsCount) >= 0;
                        newCell.Age = newCell.IsAlive ? ++newCell.Age : 0;
                        continue;
                    }
                    newCell.IsAlive = Array.BinarySearch(this.NumberOfNeighborsToBeBorn.ToArray(), aliveNeighborsCount) >= 0;
                }
            }
        }
    }
}


LifeGameクラス

ライフゲームを管理するクラスです。
マップ、生存条件、マップの描画などをつかさどります。

using System;
using System.Collections.Generic;

namespace LifeGameLibrary
{
    /// <summary>
    /// ライフゲーム
    /// </summary>
    public class LifeGame
    {
        #region コンストラクタ
        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="lc">生存条件</param>
        /// <param name="width">マップの幅</param>
        /// <param name="height">マップの高さ</param>
        /// <param name="drw">描画するやつ</param>
        public LifeGame(ILivingCondition lc, int width, int height, ICellMapDrower drw)
            : this(lc, new CellMap(width, height), drw) { }

        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="lc">生存条件</param>
        /// <param name="cm">細胞マップ</param>
        /// <param name="drw">描画するやつ</param>
        public LifeGame(ILivingCondition lc, CellMap cm, ICellMapDrower drw)
        {
            this.livingCondition = lc;
            this.CellMap = cm;
            this.cellMapDrawer = drw;
        }
        #endregion

        #region プロパティ
        /// <summary>
        /// 細胞マップを取得します。
        /// </summary>
        public CellMap CellMap { get; set; }
 
        /// <summary>
        /// 生存条件を取得します。
        /// </summary>
        private ILivingCondition livingCondition;
        public ILivingCondition LivingCondition
        {
            get { return this.livingCondition; }
        }

        private ICellMapDrower cellMapDrawer;
        public ICellMapDrower CellMapDrawer
        {
            get { return this.cellMapDrawer; }
        }
        #endregion

        #region メソッド
        /// <summary>
        /// 世代イテレータを取得
        /// </summary>
        /// <returns></returns>
        public IEnumerable<CellMap> GetCellMapGeneration()
        {
            while (true)
            {
                this.CellMap.Generation++;
                this.LivingCondition.ConfirmationAlive(this.CellMap);
                this.CellMapDrawer.Draw(this.CellMap);
                yield return this.CellMap;
            }
        }

        /// <summary>
        /// 細胞マップをランダム生成して設定します。
        /// </summary>
        public void SetRamdomCellMap() { 
        	var rnd = new Random();
            int w = this.CellMap.Width;
            int h = this.CellMap.Height;
			for(int x = 0; x < w; x++){
				for(int y = 0; y < h; y++){
                    this.CellMap[x, y].IsAlive = (Math.Floor((double)rnd.Next(2)) == 1);
				}
			}
        }

        /// <summary>
        /// 細胞マップを描画します。
        /// </summary>
        /// <returns></returns>
        public void Draw()
        {
            this.cellMapDrawer.Draw(this.CellMap);
        }

        #endregion
    }
}


Serializationクラス

CellMapのクローンを作成するために、ジェネリクスなディープコピーのみが実装されています。
このクラスに限った話ではありませんが、クラス名は適当なのでつっ込まないでください。

using System.IO;
using System.Runtime.Serialization.Formatters.Binary;

namespace LifeGameLibrary
{
    public static class Serialization
    {
        /// <summary>
        /// 対象オブジェクトのディープコピークローンを取得します。
        /// </summary>
        /// <typeparam name="T">対象オブジェクトの型</typeparam>
        /// <param name="target">コピー対象オブジェクトを指定します。</param>
        /// <returns>ディープコピーのクローンを返します。</returns>
        /// <remarks>このメソッでディープコピーするには、対象クラスがシリアライズ可能である必要があります。</remarks>
        public static T DeepCopyClone<T>(T target)
        {
            object clone = null;
            using (MemoryStream stream = new MemoryStream())
            {
                //対象オブジェクトをシリアライズ
                BinaryFormatter formatter = new BinaryFormatter();
                formatter.Serialize(stream, target);
                stream.Position = 0;

                //シリアライズデータをデシリアライズ
                clone = formatter.Deserialize(stream);
            }
            return (T)clone;
        }
    }
}


ICellMapDrowerインターフェイス

細胞マップを描画するためのインターフェイス。
こいつ見てて、クラス設計がなんか微妙な感じなことに気付きましたが、
もっかい考えるの面倒なのでこのままにしました。

namespace LifeGameLibrary
{
    /// <summary>
    /// 細胞マップを描画するやつのインターフェイス
    /// </summary>
    public interface ICellMapDrower
    {
        void Draw(CellMap cellMap);
    }
}


ConsoleDrawerクラス

こいつが細胞マップをコンソール出力してくれます。

using System;

namespace LifeGameLibrary
{
    /// <summary>
    /// コンソール出力
    /// </summary>
    public class ConsoleDrawer : ICellMapDrower
    {
        public void Draw(CellMap cellMap)
        {
            Console.Clear();
            Console.WriteLine(cellMap.GetCellMapString('■','□'));
            Console.WriteLine("世代:{0}", cellMap.Generation);
        }
    }
}

Templateクラス

ライフゲームで広く知られているパターンのテンプレを定義しています。
Wikipediaからまんま持ってきました。これは別になくてもよいですね。

using System.Collections.Generic;

namespace LifeGameLibrary.Pattern
{
    /// <summary>
    /// ライフゲームのパターンテンプレ
    /// </summary>
    public static class Template
    {
        #region 固定型
        /// <summary>
        /// ブロック
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetBlock()
        {
            yield return "□□□□";
            yield return "□■■□";
            yield return "□■■□";
            yield return "□□□□";
            yield break;
        }

        /// <summary>
        /// 蜂の巣
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetBeehive()
        {
            yield return "□■□";
            yield return "■□■";
            yield return "■□■";
            yield return "□■□";
            yield break;
        }

        /// <summary>
        /// ボート
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetBoat()
        {
            yield return "□■□";
            yield return "■□■";
            yield return "□■■";
            yield break;
        }

        /// <summary>
        /// 船
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetShip()
        {
            yield return "■■□";
            yield return "■□■";
            yield return "□■■";
            yield break;
        }

        /// <summary>
        /// 池
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetPool()
        {
            yield return "□■■□";
            yield return "■□□■";
            yield return "■□□■";
            yield return "□■■□";
            yield break;
        }
        #endregion

        #region 振動型
        /// <summary>
        /// ブリンカー
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetBlinker()
        {
            yield return "□■□";
            yield return "□■□";
            yield return "□■□";
            yield break;
        }

        /// <summary>
        /// ペンタデカスロン
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetPentadecathlon()
        {
            yield return "□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□";
            yield return "□□□□□■□□□□■□□□□□";
            yield return "□□□□■■□□□□■■□□□□";
            yield return "□□□□□■□□□□■□□□□□";
            yield return "□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□";
            yield break;
        }

        /// <summary>
        /// ヒキガエル
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetHikigaeru()
        { 
             yield return "□□■□";
             yield return "■□□■";
             yield return "■□□■";
             yield return "□■□□";
             yield break;
        }

        /// <summary>
        /// ビーコン
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetBeecon()
        {
            yield return "□□■■";
            yield return "□□■■";
            yield return "■■□□";
            yield return "■■□□";
            yield break;
        }

        /// <summary>
        /// 時計
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetClock()
        {
            yield return "□□□";
            yield return "■□■□";
            yield return "□■□■";
            yield return "□■□□";
            yield break;
        }
        #endregion

        #region 移動型
        /// <summary>
        /// グライダー
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetGlider()
        {
            yield return "□■□";
            yield return "■□□";
            yield return "■■■";
            yield break;
        }

        /// <summary>
        /// 軽量級宇宙船
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetSmallSpaceship()
        {
            yield return "□■□□■";
            yield return "■□□□□";
            yield return "■□□□■";
            yield return "■■■■□";
            yield break;
        }

        /// <summary>
        /// 中量級宇宙船
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetMiddleSpaceship()
        {
            yield return "□□□■□□";
            yield return "□■□□□■";
            yield return "■□□□□□";
            yield return "■□□□□■";
            yield return "■■■■■□";
            yield break;
        }

        /// <summary>
        /// 重量級宇宙船
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetLargeSpaceship()
        {
            yield return "□□□■■□□";
            yield return "□■□□□□■";
            yield return "■□□□□□□";
            yield return "■□□□□□■";
            yield return "■■■■■■□";
            yield break;
        }

        /// <summary>
        /// グライダー・ガン
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetGliderGun()
        {
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□■□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□■□■□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□■■□□□□□□■■□□□□□□□□□□□□■■□";
            yield return "□□□□□□□□□□□□■□□□■□□□□■■□□□□□□□□□□□□■■□";
            yield return "□■■□□□□□□□□■□□□□□■□□□■■□□□□□□□□□□□□□□□";
            yield return "□■■□□□□□□□□■□□□■□■■□□□□■□■□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□■□□□□□■□□□□□□□■□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□■□□□■□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□■■□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield return "□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□";
            yield break;
        }

        /// <summary>
        /// 汽車ぽっぽ
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetKishaPoppo()
        {
            yield return "□□□■□";
            yield return "□□□□■";
            yield return "■□□□■";
            yield return "□■■■■";
            yield return "□□□□□";
            yield return "□□□□□";
            yield return "□□□□□";
            yield return "■□□□□";
            yield return "□■■□□";
            yield return "□□■□□";
            yield return "□□■□□";
            yield return "□■□□□";
            yield return "□□□□□";
            yield return "□□□□□";
            yield return "□□□■□";
            yield return "□□□□■";
            yield return "■□□□■";
            yield return "□■■■■";
            yield break;
        }
        #endregion

        #region 長寿型
        /// <summary>
        /// ダイハード
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetDieHard()
        {
            yield return "□□□□□□■□";
            yield return "■■□□□□□□";
            yield return "□■□□□■■■";
            yield break;
        }

        /// <summary>
        /// ドングリ
        /// </summary>
        /// <returns></returns>
        public static IEnumerable<string> GetDongri()
        {
            yield return "□■□□□□□";
            yield return "□□□■□□□";
            yield return "■■□□■■■";
            yield break;
        }
        #endregion
    }
}


Programクラス

最後に、LifeGameLibraryを用いて、コンソールアプリケーションでライフゲームを実行します。
パターンテンプレはペンタデカスロンを用いています。

using System;
using LifeGameLibrary;
using LifeGameLibrary.Pattern;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            //var lifeGame = new LifeGame(StandardLivingCondition.Original,3, 3, new ConsoleDrawer());
            //lifeGame.SetRamdomCellMap();

            var lifeGame = new LifeGame(StandardLivingCondition.Original,
                           new CellMap(Template.GetPentadecathlon(), '■'), new ConsoleDrawer());

            lifeGame.Draw();
            var s = Console.ReadLine();
            foreach (var map in lifeGame.GetCellMapGeneration())
            {
                s = Console.ReadLine();
                if (s == "exit") break;
            }
        }
    }
}

以上です。そこそこオブジェクト指向していますね。初心者にもわかりやすいでしょう？
気が向いたら、いろいろ拡張したりGUIとか整備しようかな。
どうもお疲れさまでした(・ω・)

*1:雑でいい加減だったりもしますが

続・ラムダとY Combinatorと私。VBだって、やれば出来る子！

プログラミング アルゴリズム LINQ VB.NET

というわけで、前回のC#3.0で書いたラムダとY Combinatorと私。Y Combinatorは恐ろしい子。について、
VB2008のラムダ式でも書いてみました。VBだってやれば出来る子なんです(´・ω・｀)

Imports System
Imports System.Linq
Imports System.Collections.Generic

Module Module1

    Sub Main()
        'エラトステネスの篩(素数求めるやつ)
        Dim sieveOfEratosthenes As Func(Of IEnumerable(Of Integer), IEnumerable(Of Integer)) = _
            Fix(Of IEnumerable(Of Integer), IEnumerable(Of Integer))(Function(fact) Function(nums) _
                From num In nums _
                Where num = nums.First() Or num Mod nums.First() <> 0 _
                Select num _
            )

        For Each s As String In sieveOfEratosthenes(Enumerable.Range(2, 98))
            Console.WriteLine(s)
        Next
        Console.ReadLine()
    End Sub

    ''' <summary>
    ''' Y Combinator
    ''' </summary>
    Delegate Function Recursive(Of T, TResult)(ByVal f As Recursive(Of T, TResult)) As Func(Of T, TResult)
    Function Fix(Of T, TResult)(ByVal lambda As Func(Of Func(Of T, TResult), Func(Of T, TResult))) As Func(Of T, TResult)
        Dim y As Func(Of Func(Of Func(Of T, TResult), Func(Of T, TResult)), Func(Of T, TResult)) = _
        Function(f) (DirectCast((Function(g) Function(x) f(g(g))(x)), Recursive(Of T, TResult))) _
                    (DirectCast((Function(g) Function(x) f(g(g))(x)), Recursive(Of T, TResult)))
        Return y(lambda)
    End Function

End Module


C#3.0のlambda式は、式だけではなく、メソッドのように{}で囲った中にステートメントを書くことができるが、
VB2008のlambda式は、単一の式しか書くことができない点が異なる。
2chのスレなんかでは「VBのラムダ使えねぇｗ」との声が多いですね。
使えないとまでは言わないけど、マニアックなことをしたい人にはきつい制約かもかも。
ラムダ使うなら断然C#3.0といった感じ。



ついでに、匿名型に関してのC#3.0とVB2008との違いについてもちょっと言及。
C#3.0では、宣言時に初期化した内容を書き換えることができない(ReadOnly)が、
VB2008では、宣言時に初期化した内容を書き換えることができる。
VB2008で、宣言時の内容を書き換えたくないような場合はキーワード指定でReadOnlyとすることができる。
匿名型に関しては、VB2008の方が柔軟というわけか。
C#3.0の言語仕様は、なんで匿名型の内容を書き換えられないようにしたんだろう。ふーむ。



＃ん〜、今更こんなこと言うのも野暮って話なんだが、
＃VBは改行すると「_(アンダースコア)」を書かなきゃならんっちゅー仕様があるが、ここにきて邪魔な感じ。
＃普通にコード書いている分には、さほど問題にはならないが、
＃ラムダ書いたり、LINQ書くときは「_(アンダースコア)」が大量に必要になって、ウザすぎるってゆー。
＃何度もFunctionって書くのは冗長だし、ジェネリクス併用してカッコやらOfも書くとなってくると更にきっつい。
＃C#でさえ見難いのに、VBのこの見難さ(醜さ)は、マジで泣けてくるレベル。上記Y Combinatorは、その典型例だろう。
＃VBでは、ラムダとかLINQは使うなっちゅーことなんでしょうか。
＃VBユーザーいじめですか？そうじゃないと思いたい(^ω^;)



(追記:2008/08/26)

なんか無駄にややこしく書いてましたね(^ω^;)
こー書けばVBでもそこそこ見やすいかも。

    ''' <summary>
    ''' Y Combinator
    ''' </summary>
    Delegate Function Recursive(Of T, TResult)(ByVal f As Recursive(Of T, TResult)) As Func(Of T, TResult)
    Function Fix(Of T, TResult)(ByVal f As Func(Of Func(Of T, TResult), Func(Of T, TResult))) As Func(Of T, TResult)
        Dim r As Recursive(Of T, TResult) = Function(g) Function(x) f(g(g))(x)
        Return r(r)
    End Function

ラムダとY Combinatorと私。Y Combinatorは恐ろしい子。

プログラミング アルゴリズム LINQ C#3.0

再帰的な関数を作る場合に、その関数に名前をつけずに定義するにはどうすればよいの？*1
というのがY Combinatorの中心的話題のようだ。
つまり、不動点演算子を用いると、ラムダ式で再帰表現できるというお話。

f(x) = x なる x が不動点となるのであった。f(x) の具体的な式がわかれば不動点がわかるのは前述したとおりだが、わからない場合でもどうにかならないか、と考えてみる。そこで、この問題を抽象的に捉え、f(x) = x の条件を満たす x を算出する関数 g(f) を仮定してみるのだ。そうすると、f(x) = x なる x は g(f) であるので、x に g(f) を代入してもこの条件は成立するのであり、よって、f(g(f)) = g(f) が導かれる。

なんと、この f(g(f)) = g(f) が不動点演算子と呼ばれる、再帰を表す関数なのである。


元ネタフドーテンが倒せない - いげ太のブログ

Y Combinator(不動点演算子の一種)*2について、ググって勉強していました。
いろいろな記事を拝見しましたが、いげ太さんのブログの解説が自分には一番しっくりきました。
とても丁寧に解説されていて、わかりやすいです。Y Combinatorってなんぞや？って方はぜひご一読を。
(タイトルも洒落がきいてて素敵ですｗ)


C#のラムダ式でY Combinatorを書いてみる

        /// <summary>
        /// Y Combinatorみたいなやつ
        /// </summary>
        static Func<T,Fix<T,Func<Func<T,>> F)
        {
            return t => F(Fix(F))(t);
        }

元ネタ: Y Combinatorが凄すぎる！ - yuji1982の日記

確かにこのFix関数はY Combinatorと同じ動きと役割を果たしますが、
自身で自身の関数を呼んでいるので、厳密にはY Combinatorではないようです。


そこで、delegateとラムダ式を使って、C#でY CombinatorなFix関数を書いてみる。

        delegate Func<T, TResult> Recursive<T, TResult>(Recursive<T, TResult> f);
        static public Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> lambda)
        {
            Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>>
            y = f => ((Recursive<T, TResult>)(g => x => f(g(g))(x)))
                     ((Recursive<T, TResult>)(g => x => f(g(g))(x)));
            return y(lambda);
        }

え〜と・・・。なんかえらいことになってます(笑)



Y Combinatorで「エラトステネスの篩」

では、作成したFix関数で実際に、不動点演算子とラムダ式による再帰表現をしてみましょう。
題材は、Haskellで書いた「エラトステネスの篩」にしてみます。

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

namespace ConsoleApplication1
{
    static class Program
    {
        static void Main()
        {
            //エラトステネスの篩
            var sieveOfEratosthenes = Fix<IEnumerable<int>, IEnumerable<int>>(
                fact => nums =>
                {
                    return from num in nums
                           where IsPrimeNumber(num)
                           select num;
                });
            sieveOfEratosthenes(Enumerable.Range(2, 99)).ForEach(s => Console.WriteLine(s));
            Console.ReadLine();
        }
        private static bool IsPrimeNumber(this int value)
        {
            if (value < 2) return false;
            for (var i = 2; i <= value / 2; ++i)
            {
                if (value % i == 0) return false;
            }
            return true;
        }

        delegate Func<T, TResult> Recursive<T, TResult>(Recursive<T, TResult> f);
        static public Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> lambda)
        {
            Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>>
            y = f => ((Recursive<T, TResult>)(g => x => f(g(g))(x)))
                     ((Recursive<T, TResult>)(g => x => f(g(g))(x)));
            return y(lambda);
        }

        static void ForEach<T>(this IEnumerable<T> src, action)
        {
            foreach (T item in src) { action(item); }
        }
    }
}

おお、不動点演算子でラムダでLINQでエラトステネスってますね！(日本語が変)
確かにY Combinatorはすごいアルゴリズム！すごい(面白い)よこれ。


ついでにY Combinatorの引数を増やしてみる

ついでなので、引数を増やしたバージョンのY Combinatorも投下しておきます。
(引数増やしてもY Combinatorと呼んでいいのかわかんないけど。)

        /// <summary>
        /// 2つの引数をとる Y Combinator
        /// </summary>
        delegate Func<T1, Recursive<T1,(Recursive<T1, f);
        static Func<T1, Fix<T1,(Func<Func<T1,,>> lambda)
        {
            Func<Func<Func<T1,,>>,>>
            y = f => ((Recursive<T1,)(g => (a1,(g))(a1,                  ((Recursive<T1,)(g => (a1,(g))(a1,          return y(lambda);
        }

        /// <summary>
        /// 3つの引数をとる Y Combinator
        /// </summary>
        delegate Func<T1, Recursive<T1,(Recursive<T1, f);
        static Func<T1, Fix<T1,(Func<Func<T1,,>> lambda)
        {
            Func<Func<Func<T1,,>>,>>
            y = f => ((Recursive<T1,)(g => (a1,(g(g))(a1,                    ((Recursive<T1,)(g => (a1,(g(g))(a1,            return y(lambda);
        }

        /// <summary>
        /// 4つの引数をとる Y Combinator
        /// </summary>
        delegate Func<T1,> Recursive<T1,>(Recursive<T1,> f);
        static Func<T1,> Fix<T1,>(Func<Func<T1,>,t>> lambda)
        {
            Func<Func<Func<T1,>,t>>,t>>
            y = f => ((Recursive<T1,>)(g => (a1,(g(g))(a1,                    ((Recursive<T1,>)(g => (a1,(g(g))(a1,            return y(lambda);
        }

とりあえず、書いてはみたものの。なんぞこれーｗ(Func自重)
書いてみて思いました。あまり現実的ではないな、と(笑)


まとめ
Y Combinatorすげー(面白い)って思ったし、不動点を用いてラムダで再帰を表現とかって、かなりCool！なんだけども。
基本的には、クールポコよろしく「モテようとして・・、Y Combinatorを使って再帰を書いているヤツがいたんですよ。
なーにぃ！やっちまったなッ！男は黙って、普通に再帰。男は黙って、普通に再帰。」と思う次第。
C#に限って言えば、普通に再帰を書くという選択肢を選ぶことの方が、どうも一般的な感じがしてしまう。*3
理解しちゃった人には問題ないんでしょうが、一般的にどうなんよ？ってゆー可読性の心配が残るのも事実。


結論：Y Combinator・・・、恐ろしい子！



(追記:2008/08/26)
なんか無駄にややこしく書いてましたね(^ω^;)

        ///// <summary>
        ///// Y Combinator
        ///// </summary>
        delegate Func<T, TResult> Recursive<T, TResult>(Recursive<T, TResult> f);
        static public Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
        {
            Recursive<T, TResult> r = g => x => f(g(g))(x);
            return r(r); 
        }

*1:つまるところ、匿名関数の再帰のこと。

*2:不動点オペレータとか、不動点コンビネータとも言うみたい。

*3:もちろん、匿名関数の再帰はY Combinatorの方が美しいけど。

数値をアルファベット(26進数ぽ)へ変換、それはExcelのカラム名的な何か。

プログラミング アルゴリズム C#3.0

Excelをごにょごにょしていると、Excelの79列目のカラム名が「CA」だとかってのを、
取得したくなることがある。そんなときのためのブツ。こーゆーのは再帰でうまく表現できますね(^ω^)

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

namespace ConsoleApplication1
{
    static class Program
    {
        static void Main()
        {
            Enumerable.Range(1, 16384).Select(n => n.ToAlphabet()).ForEach(s => Console.WriteLine(s));
            Console.ReadLine();
        }

        /// <summary>
        /// Excelのカラム名的なアルファベット文字列へ変換します。
        /// </summary>
        /// <param name="self"></param>
        /// <returns>
        /// Excelのカラム名的なアルファベット文字列。
        /// (変換できない場合は、空文字を返します。)
        /// </returns>
        static string ToAlphabet(this int self)
        {
            if (self <= 0) return "";
            int n = self % 26;
            n = (n == 0) ? 26 : n;
            string s = ((char)(n + 64)).ToString();
            if (self == n) return s;
            return ((self - n) / 26).ToAlphabet() + s;
        }

        static void ForEach<T>(this IEnumerable<T> src, Action<T> action)
        {
            foreach (T item in src) { action(item); }
        }
    }
}

実行結果

A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
AA
AB
AC
(中略)
XCZ
XDA
XDB
XDC
XDD
XDE
XDF
XDG
XDH
XDI
XDJ
XDK
XDL
XDM
XDN
XDO
XDP
XDQ
XDR
XDS
XDT
XDU
XDV
XDW
XDX
XDY
XDZ
XEA
XEB
XEC
XED
XEE
XEF
XEG
XEH
XEI
XEJ
XEK
XEL
XEM
XEN
XEO
XEP
XEQ
XER
XES
XET
XEU
XEV
XEW
XEX
XEY
XEZ
XFA
XFB
XFC
XFD

使ったことないけど、Excel2007は16384列(カラム名「XFD」)までイケルらしい。
カラムがそんなに必要になることなんてあるんか？ｗ


(追記:2008/09/05)
ちなみにラムダ式で書くとこんな感じ

        /// <summary>
        /// Excelのカラム名的なアルファベット文字列へ変換します。
        /// </summary>
        /// <param name="self"></param>
        /// <returns>
        /// Excelのカラム名的なアルファベット文字列。
        /// (変換できない場合は、空文字を返します。)
        /// </returns>
        static string ToAlphabet(this int self)
        {
            Func<int, string> f = x =>
            {
                var s = ((char)(((x == 0) ? 26 : x) + 64)).ToString();
                return (self == x) ? s : ((self - x) / 26).ToAlphabet() + s;
            };
            return (self <= 0) ? "" : f(self % 26);
        }