javascriptalgorithmrandomselection

JS Data structure/algorithm for randomly picking from a set with reducing likelihood


I have a set of questions and want the questions to be asked "randomly". A question can be asked multiple times, including in a row. However, after a question has been asked, the likelihood of it being asked again should be reduced, so that as questions keep getting asked, the likelihood of a question that has been seen more is less, and the (relative) likelihood of a question that hasn't been seen goes up. Something like all the questions start at 1 and then after being asked it then has a likelihood of 1/2, then after a second time 1/3, etc.

Is there an established data structure/algorithm for this pattern?


Solution

  • You could assign a weight to a question and decrease it after selecting. You can select any decreasing formula you want, in my case I just decrease 1/2 every time:

    const arr = Array.from({length:20}, (_, i) => ({title: 'Question ' + (i+1), weight: 1}));
    let total = arr.length;
    
    function selectRandom(arr){      
      const rand = total * Math.random();
      let sum = 0;
      const found = arr.find(r => (sum += r.weight, rand <= sum));
      const diff = found.weight * .5;
      total -=diff, found.weight -= diff;
      return found;
    }
    
    let count=40;
    while(count--) console.log(JSON.stringify(selectRandom(arr)));