数値からランダムに値を取り出す『軽い』方法


お世話になります。

かなり初歩的な質問になってしまいますが、お許し下さい。

0から19までの連続した値があるとし、そこから重複せずに  
六つだけ取り出したいと思います。

やりたいことはたったこれだけなのですが、下記の条件を満たす方法で  
実現したいと思っています。

1.コレクションなどの機能は使用しない  
2.forやifなどといった、基本的な処理だけで実現したい  
3.取得した後も、昇順に並んでいること  
4.簡単なことだけに、極力コードを少なくしたい

これでできればと思うのですが、なかなか良い方法が見つかりません。

私が自分で一つ考えてみたのは、  
1.値を配列aに収める  
2.乱数を使って、その並び方をシャッフルする  
3.六つ分の配列bを作る  
4.上から六つだけ取得し、aからbにforで入れていく  
5.その配列をソートする  
というところまでは考えましたが、これだけのことをするのに  
5ステップも費やすのがもったいなく思ってしまいます。  
何より、一度シャッフルして再びソートするというのが無駄に思えてなりません。

これだけのことですが、もっと簡素に効率よく行える方法はありますでしょうか。

よろしくお願いします。

**転記(2016/4/13)**

# 私(argus)の回答に対するコメントになっていますが、内容的に質問欄の方が良いかと思い転記します

不甲斐ない質問で、皆様に不快な思いをさせてしまい、申し訳ありません。 言語は今のところ、C# を使用して書いていますが、この C# は仮の土台で、
将来的には別の言語、Java、もしくは php
に移植するつもりでいます。そういうこともあり、言語を絞らないで基本文系だけでというのもあり、またコレクションなどのク‌​ラスは重くなるため、少ないコードで実現できるなら、基本のアルゴリズムだけで済ませたかったというのも理由です。よって、Java
にしろ php
にしろ、コレクション系のものは使用できますが、『このクラスを使えば良い』というのではなく、アルゴリズム的に解決できる簡素な方法を模索‌​しています。…さすがに、『20
の数字はどこからきたのか』というのには、返答のしようがありませんが。




mjyさんのPython版と同じですが、i=0～19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。

i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。

[code]

    #include <stdio.h>
    #include <stdint.h>
    
    #ifdef _WIN32
    #include <intrin.h>
    #define rdtsc() __rdtsc()
    #else
    inline uint64_t rdtsc()
    {
        uint32_t hi, lo;
        __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
        return ((uint64_t)hi << 32) | (uint64_t)lo;
    }
    #endif
    
    // [0..1]の乱数
    double frand()
    {
        static uint64_t r = 123456789;
        r = r * 0x0123456789abcdef + rdtsc();
        return (double)r / UINT64_MAX;
    }
    
    int main()
    {
        int i;
        int m = 20;
        int n = 6;
        for (i = 0; n > 0 && i < m; i++) {
            if (frand() <= (double)n / (m - i)) {
                printf("%d\n", i);
                n--;
            }
        }
        return 0;
    }
    
[/code]

乱数生成の関数は間に合わせで適当に作りましたので、精度とか信用しないでください。10万回くらい回して出現頻度を見てみましたが、概ね均一に分散していると思います。

**補足**  
`frand()`（適当に実装した乱数生成関数）ですが、CPUクロックカウンタ（`rdtsc`命令）を利用している関係で、最初の1回目の`frand()`実行時のみ、結果の値が偏ります。2回目以降はまあまあ良い感じの乱数列を生成できます。上のコードのfor文の直前で`frand();`を1回実行しておくと、よりよい結果が得られます。




候補を小さい順に見ていき、選択するか否か、毎回ダイスを振れば、ランダムかつ小さい順に選択されると思います。

以下はPythonの例です。  
これがいかなる意味でランダムなのか、本当にランダムなのか、などは私は分かりません。

[code]

    #!/usr/bin/python3
    import random
    
    start = 0
    last = 19
    need = 6
    selected = 0
    
    for c in range(start, last+1):
        if random.random() <= (need - selected) / (last - c + 1):
            print(c)
            selected += 1
    
[/code]

* * *

各候補に対し毎回どういうダイスを振るか、つまりどれくらいの確率で選択するかは

[code]

    (need - selected) / (last - c + 1)
    
[/code]

で求めています。  
`(あといくつ選択する必要があるか) ／ (候補がいくつ残っているか)`  
です。  
soramimiさんの回答も参考にして下さい。

