重み付き抽選で複数を同時に取り出す場合のロジック

解決済

回答 2

投稿

  • 評価
  • クリップ 1
  • VIEW 2,906

KazukiKudo

score 34

重み付き抽選機能を実装したいと思っております。
1つを取り出す場合は、調べたら色々やり方が出てくるのですが、今回やりたいのは重みづけに従って複数を同時に取り出したい場合です。
さらにもう一つ縛りがあって、重みづけを表す割合(確率)は、整数ではなく0~1の間の小数で定義されております。

例えば以下のような連想配列(キーに対する値がその割合を示す)があったとして、これから3つを取り出す場合はどのようなプログラムになりますでしょうか?
(もちろんこの場合'5'が選ばれる確率が一番高いことになります。)

$a = array(
    '1' => 0.1,
    '2' => 0.3,
    '3' => 0.1,
    '4' => 0.1,
    '5' => 0.4
);


できればPHPでコードを示していただくのが一番嬉しいですが、ロジックがわかりやすければ何でも大丈夫です。
すみませんが、どなたかご教示の程、何卒よろしくお願い致します。

ちなみに1つの場合は以下のサイトを参考にしました。
http://lab.sonicmoov.com/development/gacha-logic/
http://pro-tyablog.blogspot.jp/2013/10/php.html
http://d.hatena.ne.jp/moroto1122/20100108/1262936688

0~1の乱数生成はこちらを参考にしました。
http://webkaru.net/php/function-mt-getrandmax/

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • yuba

    2016/03/16 18:38

    5を取り出した後、5は抽選箱に戻されるのですか、戻されないのですか?

    キャンセル

  • KazukiKudo

    2016/03/17 12:51

    戻されないです。同時に取り出すという表現をしたのですが、伝わりにくくて申し訳ございません。

    キャンセル

回答 2

checkベストアンサー

+1

やりたいことはこういうことでしょうか。

<?php
// 各要素の重み。合計して 1 になっている必要なし
$weight = array(
    '一' => 0.1,
    '二' => 0.3,
    '三' => 0.1,
    '四' => 0.1,
    '五' => 0.4
);


// 抽選を行う
function roll() {
  global $weight;
  $result = array(); // 抽選結果
  $rest = array(); // 抽選の残り要素
  foreach ($weight as $key => $w) {
    $rest[$key] = array('w' => $w);
  }
  // ここまでで各要素の重みを初期化

  for ($i = 0; $i < 3; $i++) { // 三回抽選を引く
    $limit = 0;
    foreach ($rest as $key => $val) {
      $limit += $val['w'];
      $rest[$key]['limit'] = $limit;
    }
    // ここまでで $rest の各要素ごとの累積重みを計算
    // $limit に累積重みの合計値が入る
    foreach ($rest as $key => $val) {
      $rest[$key]['limit'] = $rest[$key]['limit'] / $limit;
    }
    // ここまでで $rest の各要素ごとの正規化した累積重み X を計算
    // 0 から 1 までの乱数を発生した場合、直前の要素の X と自分の X の間に
    // 入る確率は、残っていた要素の重みの大きさに比例する
    // ので一つ選ぶ
    $rnd = lcg_value();
    $selected = null;
    foreach ($rest as $key => $val) {
      if ($rest[$key]['limit'] >= $rnd) {
        $selected = $key;
        break;
      }
    }
    unset($rest[$key]); // 選んだ要素は $rest から削除
    array_push($result, $selected);
  }
  return $result;
}

for ($i = 0; $i < 10; $i++) {
  print $i . ' --> ';
  foreach (roll() as $value) {
    print "[" . $value . "]";
  }
  print "\n";
}

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/03/17 12:53

    ありがとうございます!!試しに動かしたところ、問題なさそうです。
    コードも見やすくて大変助かります。

    キャンセル

+1

籤は無数に入っているのでしょうか?それとも固定数でしょうか?


引いても減らない
例えば例示の1~5の籤が抽選箱にそれぞれ無限に入っており、
ただ出てくる確率が「5」は40%「4」は10%である。
というなら、同時に引く個数と同じ回数、一つずつ引く抽選を行えばいいと思います。


各種1つしかない
そうではなく抽選箱にはそれそれ1つづつ合計5個の籤しか入っていない場合は
そこから複数同時に取り出すということは、抽選箱の中の籤が減っていく引き方になります。
そういう場合の抽選は籤の当選確率を固定には出来ません。
当選確率0.01%の籤でも、5つ同時に引くなら100%引き当てるからです。
こういう場合は重みを確率に変換する作業を行えば良いです。

例のリストから同時に3つ引くことを考える場合
・1つずつの抽選を3回行います。
・抽選毎に重みに従って籤の当選確率を決定します。当選率 = 対象籤の重み / 残り籤の重みの合計

1回目は
[1]1/10(0.1/1) [2]3/10(0.3/1) [3]1/10(0.1/1) [4]1/10(0.1/1) [5]4/10(0.4/1)
ランダム生成を1~10(重みの合計値)にすると簡単かも知れません。
ここで例えば「5」が引き当てられたなら

2回目は次の4つからの抽選です。
[1]1/6(0.1/0.6) [2]3/6(0.3/0.6) [3]1/6(0.1/0.6) [4]1/6(0.1/0.6)
ここで例えば「2」が引き当てられたなら

3回目は次の3つからの抽選です。
[1]1/3(0.1/0.3) [3]1/3(0.1/0.3) [4]1/3(0.1/0.3)

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/03/17 12:57

    わかりやすくロジックをご説明いただき大変ありがとうございます。勉強になりました。

    キャンセル

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

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