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

Question

前提・実現したいこと

確率に準じてランダムに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];
    }
  }
}

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

Answer 1

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

Comments

[Zuishin]

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

[Zuishin]

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

[wawawanet]

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

[Zuishin]

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

タイトルは「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;
}

Answer 5

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

Answer 6

１回目に選ばれた物が選択されないようにして，２回目の選択を行う．
（…という話だろうか）

//（乱数生成器を引数に受ける場合ってどう書くのだろうか？ 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;
}