質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.59%

確率に準じてランダムに""2つ以上の値""を""重複無く"""リストから抽出する方法は?

受付中

回答 6

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 572

score 12

前提・実現したいこと

確率に準じてランダムに1つの値をリストから抽出する方法は
https://qiita.com/mochizukikotaro/items/f93be343664a70c97c68
の改変で実装できるのですが、
例えば確率に準じてランダムに""2つ""の値を重複なくリストから抽出するとなると、どのような実装が考えられるでしょうか?

検討したこと

void SelectDouble(int &n1, int &n2) {
  int count = 5;
  int per[count];
  per[0] = 50;
  per[1] = 25;
  per[2] = 15;
  per[3] = 5;
  per[4] = 5;
  int sum = 100; // per[0] + per[1] + per[2] + per[3] + per[4]

  std::mt19937_64 mt;

  int x = mt() % sum;
  for(int i = 0; i < count; i++) {
    if(x < per[i]) {
      n1 = i;
      while(true) {
        int y = mt() % sum;
        for(int j = 0; j < count; j++) {
          if(y < per[j]) {
            n2 = j;
            if(n2 != n1) {
              return;
            }
          }
          else {
            y -= per[j];
          }
        }
      }
    }
    else {
      x -= per[i];
    }
  }
}

上記のコードは頭の悪い実装(もしかしたら実装すら出来ていない)ので、スマートな実装をご提示いただけると幸いです。
よろしくお願い致します。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 6

+1

同じコードで二回取り出せばいいのでは?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/03/22 12:26

    「重複」というのが同じ値を二回取り出すことならもう少し複雑になりますが。

    キャンセル

  • 2019/03/22 12:29

    例えば a が出る確率が 50%、b が 30% で c が 20% だとすると、最初に a が出た場合は次に b か c が出る確率が 100% になるので b が 60%、c が 40% の確率になります。他も同様です。

    キャンセル

  • 2019/03/22 12:50

    ご回答ありがとうございます。その発想はありませんでした。
    1回目で選択した値の確率を、確率の合計値から引いた値で2回目の剰余を取り、同じコードでループを回せば簡単に出来るかもしれないので検討してみます(ただ、ループのインクリメントが複雑になりそうなのが懸念事項です)

    キャンセル

  • 2019/03/22 13:06

    しかしよく考えると実用上はともかく数学的には不正確かもしれませんね。

    というのも、最初に a が出た場合は aa の組み合わせが無くなる分だけ b とc の出る確率がわずかに増えることになると思います。
    b が最初に出た場合も同じく a と c の確率が増えます。c が最初に出た場合も同様です。

    そして、最初に最も出やすいのは a で、出にくいのは c なので、結果として全体で見ると a の出る確率が減り、c の出る確率が増えることになります。

    ここまで防ぐためには、あらかじめ a を 50 個、b を 30 個、c を 20 個リストに詰めておき、それをシャッフルし、その後同じ物が続かないよう入れ替え、前から順に取り出していくのが一番簡単かなと思います。

    キャンセル

0

1回目に選ばれた物が選択されないようにして,2回目の選択を行う.
(…という話だろうか)

//(乱数生成器を引数に受ける場合ってどう書くのだろうか? templateにしたけど)
template< class RND_ENG >
int Select( const std::vector<unsigned int> &Weights, RND_ENG &rnd )
{
    std::vector<unsigned int> PSum(Weights.size());
    std::partial_sum( Weights.begin(), Weights.end(), PSum.begin() );

    unsigned int r = std::uniform_int_distribution<unsigned int>( 1, PSum.back() )( rnd );
    return std::distance( PSum.begin(), std::lower_bound( PSum.begin(), PSum.end(), r ) );
}

//main
int main(void)
{
    std::random_device rd;
    std::mt19937 MT( rd() );

    std::vector<unsigned int> Weights(5);
    Weights[0] = 50;
    Weights[1] = 25;
    Weights[2] = 15;
    Weights[3] = 5;
    Weights[4] = 5;

    const int nSelect = 2;
    for( int i=0; i<nSelect; ++i )
    {
        int selected_index = Select( Weights, MT );
        std::cout << selected_index << " ";
        Weights[ selected_index ] = 0;  //選ばれた物の確率を0にする(あるいは要素自体を削除しても良いが)
    }
    std::cout << std::endl;

    //
    std::cin.ignore();
    return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

タイトルは「2つ以上」になっているけど,とりあえず「2つ」で良いなら,まぁ,以下のような感じで.

//2つの項目を選ぶ.
//Percentages : 各要素の値は,各項目が選択される確率(%).合計が100であること.
//rnd : 乱数ジェネレータ
//戻り値:選ばれた項目indexのペア
template< class RND_ENG >
std::pair<int,int> SelectPair( const std::vector<unsigned int> &Percentages, RND_ENG &rnd )
{
    unsigned int Sum = 100*100;
    for( unsigned int v : Percentages ){    Sum -= v*v;    }
    unsigned int r = std::uniform_int_distribution<unsigned int>( 1, Sum )( rnd );

    const int N = (int)Percentages.size();
    for( int i=0; i<N; ++i )
    {
        for( int j=0; j<N; ++j )
        {
            if( i == j )continue;

            unsigned int MulW = Percentages[i] * Percentages[j];
            if( r <= MulW )
            {    return std::pair<int,int>(i,j);    }
            else
            {    r -= MulW;    }
        }
    }
    throw std::runtime_error( "!?" );
}

//main
int main(void)
{
    std::random_device rd;
    std::mt19937 MT( rd() );

    std::vector<unsigned int> Percentages(5);
    Percentages[0] = 50;
    Percentages[1] = 25;
    Percentages[2] = 15;
    Percentages[3] = 5;
    Percentages[4] = 5;

    auto result = SelectPair( Percentages, MT );
    std::cout << result.first << " , " << result.second << std::endl;

    //
    std::cin.ignore();
    return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

C++ は忘れ気味でして java で末席を汚させていただきます <(_ _;>

import java.util.*;

public class SelectDouble {

  public static void main(String[] args) {
    int[] parcent = { 50, 25, 15, 5, 5 };
    Random random = new Random(System.currentTimeMillis());

    for(int i=0; i<100; i++) {
      Set<Integer> values = selectDouble(2, parcent, random);
      System.out.println(values);
    }
  }

  static Set<Integer> selectDouble(int n, int[] parcent, Random random) {
    int[] p = new int[parcent.length];
    p[0] = parcent[0];
    for(int i=1; i<parcent.length; i++) p[i]=parcent[i]+p[i-1];
    //for(int i=0; i<p.length; i++) System.out.println(i+":"+p[i]);
    int total = p[p.length-1];

    Set<Integer> resultSet = new HashSet<>(n);
    while(resultSet.size() < n) {
      int r = random.nextInt(total);
      for(int i=0; i<p.length; i++) {
        if(r < p[i]) {
          if(!resultSet.contains(i)) resultSet.add(i);
          break;
        }
      }
    }
    return resultSet;
  }
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

#include <iostream>
#include <string>
#include <algorithm>
#include <random>

int main() {
  using namespace std;

  // カード A/B/C/D/E それぞれ 50/25/15/5/5 枚で
  // 構成されたデッキを用意し
  string deck =
    string(50,'A') +
    string(25,'B') +
    string(15,'C') +
    string( 5,'D') +
    string( 5,'E');

  // デッキをシャッフルして
  shuffle(deck.begin(), deck.end(), random_device());

  // 先頭から順に一枚ずつ読み上げる
  for ( char card : deck ) {
    cout << card;
  }
  cout << endl;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

-1

一番簡単な方法はrand関数の分bool型の配列を用意することですよ。
メモリーバカ食いするのでおすすめしませんが...

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.59%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る