[0, x)の整数に一様分布する疑似乱数を生成するとき，区間すべての整数を得るには何回ぐらい試行すればいいんですか？

わかんないヽ(°▽、°)ﾉ←

数学が出来る人は既に予想できると思うんですが，
なにぶん，自分は全く数学ができないので・・・←
シミュレーションを行うプログラムを作成し，
おおよその数を得ることにしました．

以下，結果から得られた図です．
両対数のグラフで，横軸がx，縦軸が試行回数を表しています．
xは10, 100, 1000, 10000, 100000, 1000000, 10000000で
各10回ずつシミュレーションを行いました．
プロットされているのはその平均です．
擬似乱数生成器はmt19937を使いました．
点線はgnuplotのfit（設定はデフォルト）により得られたもの．

線形．なんていうかほぼ線形関係みたいですね．
なるほど・・・．← 全然わかっていない
だいたいxの10倍の数だけ乱数を生成すれば，区間すべての整数が得られるみたいです．

重複組み合わせなどを用いて考えると10倍すれば，
まぁ，得られるんじゃね？ってことは想像できるんですが・・・ orz
例えば，n種類ある整数をm個取り出す(重複組合せの数)をnHmとすれば，
m個取り出す内，各種類必ず1つ以上選択したときの重複組合せの数はnHm-nになる．
また，nHm-n/nHmってmを大きくするとだんたん1に近づくじゃないですか．←
この値が1に近いほどそのm個取り出したときに各整数が少なくとも1つ以上含まれている
組み合わせの割合が大きくなると考えられます．
分子に注目するとnHm-nとなっていますが，m>>nになるとだんだんと
nを無視できるようになります．
このことから，ｍがnの10倍らへんで値が大幅に上昇するんじゃないかなと思います．

うん．自分の数学力ではここまでです．(´・ω・｀)
数学ができる方，教えて下さい．←

// 以下　2012年12月19日追記
おうふ

この問題はクーポン収集問題っていうらしいですね．
大学生にもなって知らないとかまじわろす・・・．
っで，全部の整数が少なくとも1回は選択されるまでの回数の期待値なんか簡単に求まるみたいですね．ちょっと詳しく書くと，0からx-1までの整数において少なくとも1回選択されている整数の数の各状態を考え，その状態に要する選択回数の期待値を足せばいいそうです．これにもたどり着けないとかまじ俺の数学力わろす・・・．具体的には，今回の問題設定の場合には期待値nは以下の式により求まります．

また近似式[1]が良い感じらしいです．ここでγはオイラーの定数（約0.5772）です．
期待値を求めてみたところ以下のようになりました．

Σ(ﾟДﾟ；)
凄い見にくいんですが，実験で得られた値と期待値はおおよそ同じ値（なんだそれ）をとっています．なるほどでした．


[1] 岩沢宏和，続確率パズルの迷宮 確率クイズ，数学セミナー，Vol.51，No.6，pp.50-55，2012．

int型の変数においてbitが立っている数に関して降順にソートする

#include <iostream>
#include <algorithm>
#include <array>
#include <bitset>

int main()
{
    std::array<int, 10> arr;
    std::generate(arr.begin(), arr.end(), []{static int index; return index++;});

    std::cout << "before: ";
    std::for_each(arr.begin(), arr.end(), [](int value){ std::cout << std::bitset<4>(value) << " "; });
    std::cout << std::endl;

    std::sort(arr.begin(), arr.end(), [](const int &l, const int &r){ return __builtin_popcount(l) > __builtin_popcount(r); });

    std::cout << "after : ";
    std::for_each(arr.begin(), arr.end(), [](int value){ std::cout << std::bitset<4>(value) << " "; });
    std::cout << std::endl;

    return 0;
}

/* Output
before: 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001
after : 0111 0011 0101 0110 1001 0001 0010 0100 1000 0000
*/

どうでもいいソース．(；´∀｀)

数学と将棋がわからない人が5五将棋の最大分岐数を求めるとこうなった

Twitterでmath26さんが以下のようなツイートをされていて
わたし、木になります！(*´∀｀*)教えて、ホータロー

問題：５五将棋の最大分岐数（ある局面で可能な指し手の数の最大値）を求めよ。（値が推測できてもそれが最大値である証明を書くのが意外と面倒かも）

— math26さん (@math26) 11月 28, 2012

分岐数は合法手の数と考えられるので，
ようは5五将棋で合法手は最大何手なのかっていう問題だと思います．
まずはホワイトボードを使って考えてみました．
すると，以下のことに気が付きました

• 相手は玉だけが一番都合がよさそう・・・
• 持ち駒はそれぞれ1種類ずつ持っていたほうがいい
• 駒を盤上に置くと打つ場所が１つ減るので，持ち駒は最大5種類であるから全体として最大で5つの合法手がなくなる

こんなことに注意しながら考えると次のような局面が得られました．

自分，打ち歩詰めに関しての知識が乏しいのですが，たぶんこの局面の分岐数は138です．（案外ある・・・

次に，この問題は玉2枚は必ず盤面上に配置し，また金銀（または成銀）飛車（または龍）角（または馬）をそれぞれ1枚ずつ盤面または駒台に配置し，残りの駒は自分側の駒台に配置した場合に，合法手の数が最大になる局面を見つけるのと同じなんじゃないかと考えました．ただし，当然その局面は相手の玉に対して利きがないものを対象とします．以下そう考えた理由が続きます・・・。

駒台には駒は1種類ずつあったほうが良い理由としては，盤上において１つの駒の合法手の最大数は利きに駒がない状態の3三馬や4三龍などで得られる12です．一方，打つ駒以外が盤面にすべて配置されていたとしても打つ合法手はおよそ14あります．このことから，駒は1種類ずつ自分の駒台にあったほうが良いと考えられます．（こう単純じゃないんかな・・・ orz）

次に歩は盤面に配置しない方がいいと考えました．盤上に配置してしまうと駒を打つ場所が１つ減ってしまいます．したがって，持ち駒の種類の数分たぶん合法手は減ります．一方，歩に関する合法手の数は最大で2です．よって，持ち駒の種類が3以上であれば歩を配置することによって最大分岐数は増加しないと考えられます．また，先に述べたように持ち駒の種類の数が多いほど種類が少ないときの場合と比べて合法手の数は減ることはないと考えられます．このことから，歩は駒台の上にあったほうがよいと考えられます．

相手は玉1枚のみが最大分岐する局面が得られやすいと考えました．これは相手の玉を配置しないで（もはや将棋じゃないけど）考えたときと配置した場合との最大分岐数が同じであれば簡単に示せそうです．なぜなら，そのような状況で相手の玉以外の駒を配置した場合に最大分岐数が増加することはおそらくないと考えられるからです．

以上の考え（仮定？）をもとにプログラムを作成し，合法手が最大となる局面を求めてみました．結果として以下の10局面2局面*が得られました．この局面はすべて合法手がたぶん138あります．（打ち歩詰めがわからない・・・）

今回，歩は自分の駒台に固定しました．また，相手に1枚渡した場合，駒台に置く以外に盤面上にも配置できることから，分岐数が138の局面は20以上あると考えられます・・・．
相手の玉を配置しない場合でも得られた最大分岐数は138でした．

また，歩（またはと）を盤面（または駒台）に配置する条件を追加した場合も同様に最大分岐数は138で，そのとき敵玉を配置しない場合でも最大分岐数は138でした．以下の図は上記で示した局面以外に得られた局面で，上の図の金がとに変わっています．これから，各駒をそれぞれ1枚ずつ任意の盤面のマスに配置（または駒台に配置）した場合における最大分岐数は138であることがわかりました．また各種類の駒を2つ盤面に配置した場合，最大分岐数は増加しないことから，たぶん5五将棋の最大分岐数は138なのではないかと思います．

寝てないこともたぶんあって，文章がスゴイヤバいですが，数学と将棋はわからない自分が求められた5五将棋の最大分岐数は138でした．

*10局面の内8局面は自玉が相手の敵玉の利きにつっこむものが含まれていました．これは反則手だそうです．将棋って奥が深い(・∀・；)　math26さんにご指摘頂きました．ありがとうございます．また，金はとに代えてもいいと助言を頂きました．(2012年12月4日修正)