php - 如何从加权列表中挑选 4 个独特的项目？

Question

所以我有一个加权项目列表，我想从这个列表中挑选 4 个不重复的项目。

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

最有效的方法是什么？我最初的尝试是，如果已经选择的项目出现，则只为后续选择重新选择……但对于一个小列表，这可能会导致大量重新选择。

编辑澄清: 对于上面的例子，忽略水果 D 到 N，总重量为 82。所以首先被采摘的机会是: ~6% B~8.5% C~14.6% O~9.8% P~61% 一旦选择了一个项目，概率就会(应该!)改变。

Answer 1

在您的评论中，您说 unique 意味着:

I don't want to pick the same item twice.

.. 并且权重决定了被选中的可能性。

要确保您不会重复选择，您需要做的就是在选择下一个之前从列表中删除最后一个选择的项目。是的，这会稍微改变您的权重，但如果您确实想要独特的结果，那么这是正确的统计更改。

---

此外，我不确定你是如何使用权重来确定候选人的，但我想出了这个算法，它应该用最少的循环来做到这一点(并且不需要根据weights，这可能会导致非常大的数组，需要 int weights 等)

我在这里使用了 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) 的一部分。在第一个循环中，你会得到这个:

• Apple — 8/20 = 0.0 到 0.4
• 橙色 — 4/20 = 0.4 到 0.6
• 香蕉 — 4/20 = 0.6 到 0.8
• 油桃 — 3/20 = 0.8 到 0.95
• Kiwi — 8/20 = 0.95 到 1.0

脚本遍历列表中的每个项目，并计算权重。当它到达包含第一个随机数的范围时，它会选择该项目，将其从列表中删除，然后根据新的总重量重新计算范围并再次运行。