2014年12月14日

C#で重複無し乱数を生成する

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その56
■問題 (出題者: raynstard さん)
整数nを渡すと1 〜 n までの整数を重複しないようランダムに出力する関数「bingo」を作ってください。

この問題は、1 〜 n までの数をシャッフルせよ、って問題と同義ですね。
.NET Framework に List<T> や IEnumerable<T>に要素をシャッフルするメソッドがあればいいんですが、無いみたいなので IEnumerable<T> の拡張メソッド Shuffle を自作しました。

Fisher-Yates shuffle アルゴリズムを採用しています。

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

namespace Doukaku.Org {
    static class ListExtentions {
        static Random rnd = new Random();
        // シャッフル拡張メソッド : Fisher-Yates shuffle アルゴリズムを採用
        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) {
            T[] result = list.ToArray();
            for (int i = result.Length - 1; i > 1; i--) {
                int j = rnd.Next(0, i);
                T a = result[i];
                result[i] = result[j];
                result[j] = a;
            }
            return result;
        }
    }
}

このShuffle メソッドがあれば、Bingoメソッドを作るのは簡単ですね。
ここでは、BingoクラスのCreate static メソッドとしました。

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

namespace Doukaku.Org {

    static class Bingo {
        // シャッフル拡張メソッド : Fisher-Yates shuffle アルゴリズムを採用
        public static IEnumerable<int> Create(int n) {
            return Enumerable.Range(1, n).Shuffle();
        }
    }
}

このメソッドがただしく動作するかどうかも以下のコードで確認しました。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            for (int x = 0; x < 40; x++) {
                var nums = Bingo.Create(20);
                foreach (int n in nums)
                    Console.Write("{0} ", n);
                Console.WriteLine(IsBingo(nums, 20));
            }
            Console.WriteLine();
            Console.ReadLine();
        }

        static bool IsBingo(IEnumerable<int> seq, int n) {
            if (seq.Count() != n)
                return false;
            for (int i = 1; i <= n; i++) {
                if (!seq.Contains(i))
                    return false;
            }
            return true;
        }
    }
}

ちなみに、Bingo.Createは、LINQ 使った以下のような実装もありますね。

public static IEnumerable<int> Create(int n) {
    var list = Enumerable.Range(1, n).OrderBy(x => rnd.Next(n));
    return list;
}



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52386804