はじめに
秘書問題（または、浜辺の美女の問題）について、D言語 を使って検証します。
D言語のソースコードは、テンプレートやRangeを使う際の参考になればと思います。
秘書問題とは
- 秘書を1人雇いたいとする。
- n 人が応募してきている。 n という人数は既知である。
- 応募者には順位が付けられ、複数の応募者が同じ順位になることはない（1位からn位まで重複無く順位付けできる）。
- 無作為な順序で1人ずつ面接を行う。次に誰を面接するかは常に同じ確率である。
- 毎回の面接後、その応募者を採用するか否かを即座に決定する。
- その応募者を採用するか否かは、それまで面接した応募者の相対的順位にのみ基づいて決定する。
- 不採用にした応募者を後から採用することはできない。
- このような状況で、最良の応募者を採用することが問題の目的である。
浜辺の美女の問題とは
- ｎ人の美女が海辺に並んでいるとする。
- それを端から見て行き、一人だけ選択できる。
- 後戻りは許されないものとする。
- 順位の期待値を最小にする選び方を求めることが問題の目的である。
検証用のソースコード
答えはすでにわかっていて、これをプログラムで検証します！！
nが20の場合は、以下が最善とされています。
１）最初の5人は見るだけで選択しない。
２）次の5人については、それまでで1位であれば、選択する。
３）次の3人については、それまでで2位以内であれば、選択する。
４）次の2人については、それまでで3位以内であれば、選択する。
５）16番目の人が、それまでで4位以内であれば、選択する。
６）17番目の人が、それまでで5位以内であれば、選択する。
７）18番目の人が、それまでで7位以内であれば、選択する。
８）19番目の人が、それまでで10位以内であれば、選択する。
９）最後までくれば、その人を選択する。
import std.stdio;
struct Combinations(T) {
import std.traits: Unqual;
Unqual!T[] pool, front;
size_t[] index;
size_t n, r;
bool empty = false;
this(T[] pool_, in size_t r_) pure nothrow @safe {
this.pool = pool_.dup;
this.n = pool.length;
this.r = r_;
if (r > n){
empty = true;
}
front.length = r;
index.length = r;
foreach ( i; 0 .. r){
front[i] = pool[i];
index[i] = i;
}
}
void popFront() pure nothrow @safe {
if (!empty) {
bool broken = false;
size_t pos;
foreach_reverse (immutable i; 0 .. r) {
pos = i;
if (index[i] != i + n - r) {
broken = true;
break;
}
}
if (!broken) {
empty = true;
return;
}
index[pos]++;
foreach (immutable i; pos + 1 .. r){
index[i] = index[i - 1] + 1;
front[i] = pool[index[i]];
}
front[pos] = pool[index[pos]];
}
}
}
Combinations!(T) combinations(T)(T[] items, in size_t k)
{
return typeof(return)(items, k);
}
double judge(int[] mem, int cond, double next)
{
int now = mem[0];
for ( int i = 1; i < mem.length; i++ ){
if ( mem[0] > mem[i] ){
now--;
}
}
return ( (now <= cond) ? mem[0] : next );
}
void analyze(int n)
{
import std.algorithm : fold;
import std.algorithm.comparison : min;
import std.algorithm.mutation : swap;
import std.algorithm.sorting : nextPermutation;
import std.range: array, iota;
double expect; // 次回以降の期待値
double[] ranksum; // 〇位を選んだ場合の期待値集計
ranksum.length = n + 1;
int upper = n; // upper以下の順位を選択する必要なし
for ( int remain = 2; remain <= n; remain++ ){ // remain : 残り人数
ranksum[] = 0.0;
long count = (cast(long)n - remain + 1).iota(n + 1).fold!("a * b");
if ( remain == 2 ){
foreach ( members; 1.iota(n + 1).array.combinations(remain) ){
do {
for ( int i = 1; i <= upper; i++ ){
ranksum[i] += members.judge(i, members[1]);
}
} while ( members.nextPermutation );
}
} else {
long c = 1L.iota(remain).fold!("a * b");
foreach ( members; 1.iota(n + 1).array.combinations(remain) ){
auto m = members.dup;
for ( int j = 0; j < m.length; j++ ){
swap(m[0], m[j]);
for ( int i = 1; i <= upper; i++ ){
ranksum[i] += m.judge(i, expect) * c;
}
}
}
}
int bestcond;
double bestrank = n;
for ( int i = 1; i <= min(upper, n - remain + 1); i++ ){
double rank = ranksum[i] / count;
if ( bestrank >= rank ){
bestcond = i;
bestrank = rank;
}
writefln("%4d %.2f %f", i, ranksum[i], rank);
}
writefln("%2d人目(残り%2d人) %d位以内を選ぶ 期待値: %f",
n - remain + 1, remain, bestcond, bestrank);
expect = bestrank;
if ( expect < upper ){
upper = cast(int)expect;
}
}
}
void main()
{
const int N = 20; // 全体の人数
analyze(N);
}
ソースコード補足説明
struct Combinations(T)は、組み合わせを取得するための構造体です。
empty、front、popFrontを用意することで、Rangeの仕組みを利用しています。
D言語 Rangeについて
judgeは、ある条件で採用した場合の順位（期待値）を返す関数です。
ある条件とは 今回の応募者（mem[0]）がそれまでの応募者の中でcond位以上であることです。
戻り値は、採用した場合はmem[0]の本当の順位、採用しない場合は以降の面接での期待値です。
analyzeは、n回目(19～1)の面接での期待値を算出します。
19人目(残り2人)の面接から、前にさかのぼって、ループで検証しています。
foreachループの中でjudgeを呼び出しています。それまでの応募者の中でi位以上の順位を採用した場合の期待値をに算出します。
foreachループから抜けた後で、最も期待値が低い（順位がよい）場合のiを判定します。
結果の検証
・・・
8 3066.00 8.068421
9 3045.00 8.013158
10 3045.00 8.013158
11 3066.00 8.068421
12 3108.00 8.178947
・・・
19人目(残り 2人) 10位以内を選ぶ 期待値: 8.013158
８）19番目の人が、それまでで10位以内であれば、選択する。
19人目(残り2人)の面接では、それまでの10位以内を採用するのが最善で期待値は8.013158位となります。
一般的に言われている回答の他に、それまでの9位以内を採用するという判断でも期待値は変わらないようです。
18人目(残り 3人) 7位以内を選ぶ 期待値: 6.616228
17人目(残り 4人) 5位以内を選ぶ 期待値: 5.699690
16人目(残り 5人) 4位以内を選ぶ 期待値: 5.046827
15人目(残り 6人) 3位以内を選ぶ 期待値: 4.562461
14人目(残り 7人) 3位以内を選ぶ 期待値: 4.184791
13人目(残り 8人) 2位以内を選ぶ 期待値: 3.887131
12人目(残り 9人) 2位以内を選ぶ 期待値: 3.643122
11人目(残り10人) 2位以内を選ぶ 期待値: 3.458009
10人目(残り11人) 1位以内を選ぶ 期待値: 3.303117
9人目(残り12人) 1位以内を選ぶ 期待値: 3.169437
1 1479496150084026.25 3.064924
2 1569838714977385.50 3.252078
3 1800974220157852.75 3.730898
8人目(残り13人) 1位以内を選ぶ 期待値: 3.064924
1 10144113363085170.00 3.002078
2 11198890138231282.00 3.314232
3 13520803375955872.00 4.001385
7人目(残り14人) 1位以内を選ぶ 期待値: 3.002078
1 60857658516276512.00 3.001732
2 70987728554643248.00 3.501385
3 91254890293743376.00 4.501039
6人目(残り15人) 1位以内を選ぶ 期待値: 3.001732
７）18番目の人が、それまでで7位以内であれば、選択する。
６）17番目の人が、それまでで5位以内であれば、選択する。
５）16番目の人が、それまでで4位以内であれば、選択する。
４）次の2人については、それまでで3位以内であれば、選択する。
３）次の3人については、それまでで2位以内であれば、選択する。
２）次の5人については、それまでで1位であれば、選択する。
以降、一般的に言われている回答の通りに、採用するという判断が正しいことが検証できています。
6人目(残り15人) 1位以内を選ぶ 期待値: 3.001732
1 314390275970090559.99 3.101385
2 395451901263708543.99 3.901039
3 547473168462892096.01 5.400693
5人目(残り16人) 1位以内を選ぶ 期待値: 3.101385
4人目(残り17人) 1位以内を選ぶ 期待値: 3.376039
3人目(残り18人) 1位以内を選ぶ 期待値: 4.000693
2人目(残り19人) 1位以内を選ぶ 期待値: 5.500346
1人目(残り20人) 1位以内を選ぶ 期待値: 10.500000
１）最初の5人は見るだけで選択しない。
5人目(残り16人)では、それまでの1位以内を採用するのが最善ですが、6人目(残り15人)で1位を採用できたときより期待値が高い（順位がよくない）ことがわかります。それより前（1人目～4人目）の面接でも、同様です。
結果的に、最初の5人は見るだけで採用しないのが、最善となります。
検証終わりです。
参考情報