2014年12月26日

C#でn人の中から公平にm人を選ぶ

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その59


■問題 (出題者:にしお さん)
n人の中から公平にm人を選ぶ、くじ引きプログラムを作ってください。

まず、このプログラムの内部で使う「n個からm個を選ぶメソッド」を考えてみます。
このメソッドのインターフェースは、以下の2つがが考えられます。
IEnumerable<T> DrawLots<T>(IList<T> bag, int m)

IEnumerable<int> DrawLots(int n, int m)

前者は、数値に限定しないメソド、後者は、全体の個数を渡すメソッド。
前者の場合は、重複無し乱数で作成した Shuffle拡張メソッドを使えば、

IEnumerable<T> DrawLots<T>(IList<T> bag, int m) {
    return bag.Shuffle().Take(m);
}

と書けますが、bag の要素数が多い場合、例えば、100万人から3人選ぶみたいな 場合は、すべてをシャッフルするのはどう考えても無駄です。
なので、別のやり方も考えて見ました。

        static IEnumerable<T> DrawLots<T>(IList<T> bag, int m) {
            Random rnd = new Random();
            var result = new List<int>();
            while (result.Count < m) {
                int j = rnd.Next(0, bag.Count);
                if (!result.Contains(j)) {
                    result.Add(j);
                    yield return bag[j];
                }
            }
        }

答えをすべて覚えておかなければなりませんが、Shuffle するよりはましかなと 思います。 でも、100万人から90万人選ぶみたいなケースだと、このコードもあまり良くないです。
その場合、どういったコードが適切なのか難しいですね。
ちなみに、result は、LIst<T>ではなく、Dictionary<int,bool>でも良いですね。


後者のメソッドの場合だと、

        static IEnumerable<int> DrawLots(int n, int m) {
            Random rnd = new Random();
            var result = new List<int>();
            int i = 0;
            while (result.Count < m) {
                int j = rnd.Next(0, n);
                if (!result.Contains(j)) {
                    result.Add(j);
                    yield return j;
                }
            }
        }
先ほどのコードと本質は同じです。
以下は、上記2つのメソッドの使い方を示すコード。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var r = DrawLots(new List<char> { 'a','b','c','d','e','f','g','h','i','j','k','l' },5);
            r.ToList().ForEach(Console.WriteLine);
            Console.ReadLine();

            var r2 = DrawLots(100, 5);
            r2.ToList().ForEach(Console.WriteLine);
            Console.ReadLine();
        }
    }
}


たぶん、これが今年最後の投稿です。
来年も懲りずに、このどう書く? org シリーズを継続していくつもり。

それでは皆さん良いお年を。




 

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

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