23978


お世話になります。

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

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
の数字はどこからきたのか』というのには、返答のしようがありませんが。


CC BY-SA 3.0
2016-04-12T09:15:00.133
23948
2016-04-13T14:15:30.630
2016-04-13T09:28:03.407
9374
question
アルゴリズム
数値からランダムに値を取り出す『軽い』方法


シャッフル方法などにもよるかと思いますが、  
配列aの構造を壊したくない？…であれば配列bに移し  
配列bをソート状態のまま乱数配列に近づければいいのでは？

１．値を配列aに収める  
２．配列aを配列bにディープコピー(1の段階でbを作成してもいい)  
３．配列長の乱数を作成し、その要素を必要数になるまでDeleteしていく  
(Deleteするたび乱数長は1ずつ短くなるので乱数を出しなおしながらDelete)


CC BY-SA 3.0
2016-04-12T09:31:21.240
23951
2016-04-12T09:31:21.240
23948
answer


以下の流れでソートしながら配列に流し込むシンプルなコードをC#で書いてみました。

  1. 乱数の最大値を19→18→17...と減らしながら取得する
  2. 取得済みの値より乱数の値が大きい場合は乱数をインクリメントして重複を回避する
  3. 配列にソートしながら格納する

コードを減らす意味でもバグを回避する意味でもコレクションやArray.Sortを使った方が良いと思いますが…。

[code]

    using System;
    using System.Linq;
    
    namespace ConsoleApplication1
    {
        class Program
        {
            static void Main(string[] args)
            {
                GetRandomArray(6).ToList().ForEach(i => Console.WriteLine(i));
                Console.Read();
            }
    
            /// <summary>
            /// 無作為に重複のない0-19の整数を任意の個数取得する
            /// </summary>
            /// <param name="count">取得する数値の個数</param>
            /// <returns></returns>
            private static int[] GetRandomArray(int count)
            {
                const int MAX_VALUE = 19;
                var result = new int[count];
                var rnd = new Random();
                for (var i = 0; i < count; i++)
                {
                    //未設定の値として-1で初期化
                    result[i] = -1;
                    //乱数の最大値をiに応じて減らしつつ、標本を取得
                    var sample = rnd.Next(MAX_VALUE + 1 - i);
                    //配列の先頭からi個分の値をソートしながら埋めていく
                    for (var j = 0; j <= i; j++)
                    {
                        if(result[j] < 0)
                        {
                            //未設定の値ならそのまま乱数をセット
                            result[j] = sample;
                        }
                        else if(sample < result[j])
                        {
                            //標本が配列の値より小さければ並べ替え
                            var swap = result[j];
                            result[j] = sample;
                            sample = swap;
                        }
                        else
                        {
                            //標本が配列の値より大きければインクリメントして重複を避ける
                            sample++;
                        }
                    }
                }
                return result;
            }
        }
    }
    
[/code]


CC BY-SA 3.0
2016-04-12T10:42:51.883
23954
2016-04-12T10:42:51.883
9820
23948
answer


低水準言語で比較的簡単に実装できることを考えました．

1． 長さが20の配列`a`をつくる． すべての要素を0にセットする．  
2． 0~19までの乱数`r`を生成する． インデックス`r`の要素を1にする`a[r]=1`.これを6回くりかえす  
3\. 配列`a`の総和を計算する． これを`s`とする． `s`が6でなければ6になるまで2の手順をする.  
4\. 配列`a`を順番にたどって`a[i]`が1であるインデックス`i`を出力

わかりにくいのでCのコードだと`a`以上`b`以下の乱数を生成する関数を`random(a,b)`として

[code]

    int a[20];
    for( int i=0;i<20;i++ ) a[i] = 0;
    
    int s = 0;
    while( s != 6 ){ // 選ばれた数が6個になるまで
      int r = random(0,19);
      a[r] = 1;
      s = 0;
      for( int i=0;i<20;i++ ) s += a[i]; 
    }
    
    for( int i=0;i<20;i++ )
      if( a[i]==1 ) printf("%d\n",i);
    
[/code]


CC BY-SA 3.0
2016-04-12T11:12:53.010
23956
2016-04-12T11:12:53.010
14418
23948
answer


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

以下は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さんの回答も参考にして下さい。


CC BY-SA 3.0
2016-04-12T11:36:37.613
23957
2016-04-13T03:37:48.273
2016-04-13T03:37:48.273
3054
3054
23948
answer


「コレクション」が指すモノは言語により変わるでしょうが、広義には配列(array)もコレクションの一種と言えます（言えてしまいます）。

ひねくれた回答として、ビット位置を利用したアルゴリズムを書いてみました。ただし、これも見方によっては整数型を「ビットの集合体（コレクション）」とみなしているだけです。

[code]

    #include <stdio.h>
    #include <stdlib.h>
    
    #define N 20  // 個数
    #define M 6   // 選択数
    
    int main()
    {
      unsigned bin = 0; // 選択を表すビット列
      int n = 0;        // ビット1を立てたカウンタ
    
      // Mビットを選択するまで下記を繰り返し:
      while (n < M) {
        // Nビット中からランダムに1ビットを選択する
        unsigned c = 1U << (rand() % N);
        // 選んだビット位置がまだビット0ならば;
        if ((bin | c) != bin) {
          // 該当ビット位置に1を設定して
          bin |= c;
          // カウンタを+1
          ++n;
        }
      }
    
      // ビット1が立っている値を昇順出力
      for (n = 0; n < N; n++) {
        if (bin & (1U << n))
          printf("%d\n", n);
      }
    }
    
[/code]

[動作するデモ](http://melpon.org/wandbox/permlink/XMfhzJFPNM83bu95)


CC BY-SA 3.0
2016-04-12T11:38:19.017
23958
2016-04-12T11:38:19.017
49
23948
answer


それでは Ruby で。

[code]

    r = Random.new
    [*[*0..19].combination(6)][r.rand((15..20).inject(:*)/(1..6).inject(:*))]
    
[/code]

見ての通り効率が悪いので参考程度にどうぞ。

**追加**

既に承認済みではありますけれども、思い付いた事があるので追加します。

上記の Ruby のコードでは組み合わせの全てを配列として生成しているので非効率極まりないわけですが、組み合わせの総数は予め計算可能で(この場合は
38760 通り)、昇順という条件から順序も決まっています。なので 0 ~ 38759
の範囲の数値から、その順番に該当する組み合わせを導出する事も可能です。

`Java` か `PHP` を考えているとの事ですので `Java` で書いてみました。

**Sampling.java**

[code]

    import java.util.Random;
    
    class Sampling {
      public static int numberOfCombinations(int n, int m) {
        int u = n; int v = m;
        for (int i=1;i<m;i++) {
          u *= n - i; v *= m - i;
        }
        return u/v;
      }
    
      public static void main(String[] args) {
        int n = 20; int m = 6;
    
        Random rnd = new Random();
        int r = rnd.nextInt(numberOfCombinations(n, m));
    
        int x = 0;
        for (int i=1;i<m;i++) {
          int j = 1; int sum = 0; int sum_prev = 0;
          while (r >= sum) {
            sum_prev = sum;
            sum += numberOfCombinations(n-j, m-i);
            j++;
          }
          x += j - 2;
          System.out.printf("%d,", x++);
          n -= j - 1; r -= sum_prev;
        }
        System.out.println(x + r);
      }
    }
    
[/code]


CC BY-SA 3.0
2016-04-12T13:09:45.053
23962
2016-04-13T12:15:02.147
2016-04-13T12:15:02.147
23948
answer


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回実行しておくと、よりよい結果が得られます。


CC BY-SA 3.0
2016-04-13T03:05:29.173
23978
2016-04-13T14:15:30.630
2016-04-13T14:15:30.630
3337
3337
23948
answer