4

重み付けされたアイテムのリストがあり、このリストから重複していないアイテムを 4 つ選びたいと思います。 

Item     Weight
Apple     5
Banana    7
Cherry    12
...
Orange    8
Pineapple 50

これを行う最も効率的な方法は何ですか? 私の最初の試みは、すでにピックされたアイテムが出現した場合に、後続のピックを再ロールすることでした...しかし、小さなリストの場合、これにより大量の再ロールが発生する可能性があります.

明確化のために編集: 上記の例では、果物 D から N までを無視すると、合計重量は 82 になります。したがって、最初に選択される可能性は次のとおりです: A ~6% B ~8.5% C ~14.6% O ~9.8% P ~61% アイテムが選択されると、確率が変わる (はずです!)。

4

4 に答える 4

6

あなたのコメントでは、一意の意味は次のとおりです。

同じものは二度と選びたくない。

..そして、重みが選ばれる可能性を決定すること。

重複を選択しないようにするために必要なことは、次のアイテムを選択する前に、最後に選択したアイテムをリストから削除することだけです。はい、これにより重みがわずかに変更されますが、一意の結果が必要な場合は、これが正しい統計変更です。

さらに、候補を決定するために重みをどのように使用しているかはわかりませんが、最小数のループでこれを行う必要があるこのアルゴリズムを思いつきました (重みに従って配列を埋める必要はありません。非常に大きな配列になる可能性があり、int の重みが必要になるなど)

ここでは JavaScript を使用しました。これは、サーバーなしでブラウザーで出力を簡単に確認できるようにするためです。複雑なことは何もしていないので、PHP への移植は簡単です。

定数

var FRUITS = [
    {name : "Apple", weight: 8 },
    {name : "Orange", weight: 4 },
    {name : "Banana", weight: 4 },
    {name : "Nectarine", weight: 3 },
    {name : "Kiwi", weight: 1 }
];

var PICKS = 3;

function getNewFruitsAvailable(fruits, removeFruit) {
    var newFruits = [];
    for (var idx in fruits) {
        if (fruits[idx].name != removeFruit) {
            newFruits.push(fruits[idx]);
        }
    }
    return newFruits;
}

脚本

var results = [];
var candidateFruits = FRUITS;

for (var i=0; i < PICKS; i++) {
    // CALCULATE TOTAL WEIGHT OF AVAILABLE FRUITS
    var totalweight = 0;
    for (var idx in candidateFruits) {
        totalweight += candidateFruits[idx].weight;
    }
    console.log("Total weight: " + totalweight);

    var rand = Math.random();

    console.log("Random: " + rand);

    // ITERATE THROUGH FRUITS AND PICK THE ONE THAT MATCHES THE RANDOM
    var weightinc = 0;
    for (idx in candidateFruits) {
        // INCREMENT THE WEIGHT BY THE NEXT FRUIT'S WEIGHT
        var candidate = candidateFruits[idx];
        weightinc += candidate.weight;

        // IF rand IS BETWEEN LAST WEIGHT AND NEXT WEIGHT, PICK THIS FRUIT
        if (rand < weightinc/totalweight) {
            results.push(candidate.name);
            console.log("Pick: " + candidate.name);

            // GET NEXT SET OF FRUITS (REMOVING PICKED FRUIT)
            candidateFruits = getNewFruitsAvailable(candidateFruits, candidate.name);
            break;
        }
    }
    console.log("CandidateFruits: " + candidateFruits.length);
};

出力

for (var i=0; i < results.length; i++) {
    document.write(results[i] + "<br/>");
}

基本的な戦略は、各果物に全範囲の一部を割り当てることです[0,1)。最初のループでは、次のようになります。

  • りんご— 8/20 = 0.0 ～ 0.4
  • オレンジ— 4/20 = 0.4 ～ 0.6
  • バナナ— 4/20 = 0.6 ～ 0.8
  • ネクタリン— 3/20 = 0.8 ～ 0.95
  • キーウィ— 8/20 = 0.95 ～ 1.0

スクリプトはリスト内の各項目を繰り返し処理し、重量カウンターを進めます。最初の乱数を含む範囲に到達すると、そのアイテムが選択され、リストから削除され、新しい総重量に基づいて範囲が再計算され、再度実行されます。

于 2011-06-23T18:42:50.267 に答える
1

ここで、次の手順のアイデアを見つけました。

  1. 重みの合計を作成します --> SUM
  2. 0 から SUM までの乱数を作成 --> RAND_NUMBER
  3. リストを反復処理し、各要素の重みを RAND_NUMBER から減算します。RAND_NUMBER が負になる場合、最初の要素があります。
  4. 見つかった要素をリストから削除し、要素が 4 つになるまでステップ 1 に戻ります。
于 2011-06-23T18:52:15.637 に答える
1

アップデート

function array_rand2($ary,$n = 1)
{
  // make sure we don't get in to an infinite loop
  // check we have enough options to select from
  $unique = count(array_unique(array_keys($ary)));
  if ($n > $unique) $n = count($unique);

  // First, explode the array and expand out all the weights
  // this means something with a weight of 5 will appear in
  // in the array 5 times
  $_ary = array();
  foreach ($ary as $item => $weight)
  {
    $_ary = array_merge($_ary, array_fill(0, $weight, $item));
  }

  // now look for $n unique entries
  $matches = array();
  while (count($matches) < $n)
  {
    $r = $_ary[array_rand($_ary)];
    if (!in_array($r,$matches))
    {
      $matches[] = $r;
    }
  }

  // and now grab those $n entries and return them
  $result = array();
  foreach ($matches as $match){
    $result[] = $match;
  }
  return $result;
}

それがより良い仕事をするかどうかを確認してください。

于 2011-06-23T18:30:59.460 に答える
0

たぶん、「リロール」の代わりに、ランダムに生成したリスト要素のインデックスをインクリメントすることができます: list.elementAt(rand_index++ % size(list))(そのようなもの)。そのようなロジックを使用すると、次のランダムな一意のアイテムをかなり高速に見つけることができると思います.

もちろん、通常はもっと良い解決策があると思います。

編集：ブラッドがすでに提供しているようです.. :)

于 2011-06-23T18:31:16.603 に答える