8

お世話になります。

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

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

7
  • 4
    「コレクションなどの機能」の具体例がよくわかりませんが、配列のシャッフルやソートはそこには含まれないのでしょうか。また、コードの長さや実装の容易さを気にされるのであれば、言語の指定があるとよいのではないでしょうか。
    – unarist
    Commented 2016年4月12日 9:23
  • 2
    配列のシャッフルは結構高レベルの操作なので、「コレクションなどの機能は使用しない」と矛盾します。既に付いている回答をみても、中間要素を落としているのでこれは「コレクションの機能を使用しない」に抵触しているかもしれません。想定している言語、なぜこれが必要なのかと言う情報、あなたが実際に書いて見たコード、があれば良い質問に近づけると思います。
    – suzukis
    Commented 2016年4月12日 10:35
  • 3
    あと、「0~19の連続した値」という条件は絶対なのでしょうか。20個なら成立しても10000個とかだと成立しない回答持ついてしまっていますし、20個が絶対なのであればアルゴリズム云々を気にするほどの話でもないです。
    – suzukis
    Commented 2016年4月12日 12:25
  • 7
    質問にクローズ票を投じます。オフトピックである理由: アルゴリズムが聞きたいのか、具体的にこの問題インスタンスがときたいのか。具体的な場合には、コレクションを使わない理由は何なのか。アルゴリズムの場合には、 20 の数字はどこからきたのか。
    – Yuki Inoue
    Commented 2016年4月12日 13:59
  • 3
    回答される方へ:この手の質問(と回答)についてメタに投稿しました。ご意見お寄せいただけると幸いです。 meta.ja.stackoverflow.com/q/2176/8000
    – unarist
    Commented 2016年4月12日 14:45

7 件の回答 7

6

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

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

#!/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

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

(need - selected) / (last - c + 1)

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

1
  • 1
    この方法ですべてのパターンが同確率で生成されそうです.数値的には確認できました.解析的に証明できそうですが,いま一歩でつまってしまいました.
    – takoika
    Commented 2016年4月13日 10:43
5

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

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

#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;
}

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

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

1
  • ありがとうございました。 今回の件は、私の質問も悪かったため、混乱をさせてしまって申し訳なく思っています。 そんな中でしたが、soramimiさんのこの回答が、一番良いと思いました。ありがとうございました。ほかの皆様方も、回答いただきありがとうございます。 次回からは質問にも気をつけますので、今後ともよろしくお願いいたします。 Commented 2016年4月13日 5:45
2

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

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

#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);
  }
}

動作するデモ

1

それでは Ruby で。

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

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

追加

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

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

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

Sampling.java

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);
  }
}
4
  • Rubyなら[*0..19].sample(6).sortでいいのではないかと思います
    – suzukis
    Commented 2016年4月13日 3:30
  • sort の類は使わないという条件(があるのかどうかは不明ですが)で…
    – user9156
    Commented 2016年4月13日 3:35
  • 不甲斐ない質問で、皆様に不快な思いをさせてしまい、申し訳ありません。 言語は今のところ、C#を使用して書いていますが、このC#は仮の土台で、 将来的には別の言語、Java、もしくはphpに移植するつもりでいます。そういうこともあり、言語を絞らないで基本文系だけでというのもあり、またコレクションなどのクラスは重くなるため、少ないコードで実現できるなら、基本のアルゴリズムだけで済ませたかったというのも理由です。 よって、Javaにしろphpにしろ、コレクション系のものは使用できますが、『このクラスを使えば良い』というのではなく、アルゴリズム的に解決できる簡素な方法を模索しています。…さすがに、『20 の数字はどこからきたのか』というのには、返答のしようがありませんが。 Commented 2016年4月13日 4:33
  • まず追加情報は質問本文を修正することで追加してください。コメント欄ですと回答が増えるに連れ埋もれ回答者に伝わりにくくなります。また、質問に対するコメントで『20 の数字はどこからきたのか』と質問がありましたが、おそらくそれは「ループで生成する数値なのか?」「定数で持っているデータ」なのかというデータの発生元についての質問かと思われます。
    – user10259
    Commented 2016年4月13日 5:15
0

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

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

0

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

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

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

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;
        }
    }
}
0

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

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)として

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);

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。