根据该行的“权重”随机选择行

Question

I have a table like this:

ID chance
1 1
2 2
3 4
4 1

Now I need to choose a rand() from this table

SELECT * FROM table
ORDER BY RAND()
LIMIT 1

But ID #2 has double the chances to be selected compared to ID #1 AND 4. Likewise ID #3 has four times the chances to be selected compared to ID #1 AND 4.

Somewhat similar to lottery based on chance.

Answer 1

This is how lottery works in some of the games. Given table similar to your example (say, we also have chance column that indicated value-based possibility of getting this particular reward), the algorithm is:

1. Calculate total lottery value (in your example it is 1 + 2 + 4 + 1 = 8).
2. Generate a value that is from range 1..max (max is 8 in current example) inclusive.
3. Iterate over all items from rewards list to find the one item where sum of all previous chances is more than generated number but less or equal than

Say, we have generated number 5. Our comparison steps are:

1. 0 < 5 <= (0) + 1 is false so ID1 is not what we get. Left side is 0 because we start our calculations from 0.
2. 1 < 5 <= (1) + 2 is false so ID2 is not what we get.
3. 1 + 2 < 5 <= (1 + 2) + 4 is true so we get ID3.

Example in JavaScript:

var rewards = [
  { id: 1, chance: 1 },
  { id: 2, chance: 2 },
  { id: 3, chance: 4 },
  { id: 4, chance: 1 }
];

function getRandomInt(min, max) {
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function generate() {
  var sum = 0;
  var next_sum = 0;
  var random = getRandomInt(1, rewards.reduce(function(pv, cv) {
    return pv + cv.chance;
  }, 0));

  for (var i = 0; i < rewards.length; i++) {
    next_sum = sum + rewards[i].chance;
    if ((random > sum) && (random <= next_sum)) {
      return rewards[i].id;
    }
    sum += rewards[i].chance;
  }
}

var winnerCounts = {}, i, winner;
for (i = 0; i < 8000; i++) {
  winner = generate();
  winnerCounts[winner] = (winnerCounts[winner] || 0) + 1;
}
console.log("Number of times each id was selected after %d itrations", i);
console.log(winnerCounts);

</div>