1

I did research and found the algorithm for small lists in general. I have some arrays such:

arr = [1,2,3,4 .... , 96,97,98,99,100];

arr2 = [105, 110, 165, 170];

arr3 = [1,2,7,8,9];

I want to send these arrays to a function and get random numbers from this array, but I want to have a higher probability of getting bigger numbers every time.

For example in array 1, the probability of 96 should be more than 4, but the probability of 97 should be more than 96.

How to generate a random weighted distribution of elements

Usually the solutions are like in this topic. However, this can cause performance problems with my arrays.

How can I achieve that?

Dokksen
  • 372
  • 1
  • 4
  • 17
Zagano
  • 99
  • 1
  • 10
  • why *"96 should be more than 4,"* and the next at least of the predecessor? – Nina Scholz Aug 19 '20 at 08:10
  • use numpy or random models ?https://numpy.org/doc/stable/reference/random/generated/numpy.random.choice.html – Oscar Aug 19 '20 at 08:12
  • What should be the difference in probability between the numbers? Should it be equivalent to their index in a sorted array? Like `100` is 100 times more likely to be picked compared to `1`? – adiga Aug 19 '20 at 08:16
  • @NinaScholz Since 96 is bigger than 4, it should be more likely to come. This is just one example. – Zagano Aug 19 '20 at 08:16
  • @adiga Actually, there is no such condition or requirement. For example, while the probability of a 1 in array 3 is 10%, the probability of a 9 may be 30%. This can vary. – Zagano Aug 19 '20 at 08:21
  • Make probability proportional to value, i.e. divide array by sum of all values and then normalize and you have your probabilities – Severin Pappadeux Aug 19 '20 at 12:19

1 Answers1

2

You could calculate the probabilities and pick the value.

For using it with a custom array take random

getRandomValue = random(sortedArray),

and later in a loop

let value = getRandomValue();


const
    random = sortedValues => {
        let length = sortedValues.length,
            sum = length * (length + 1) / 2;

        return () => {
            let r = Math.random();
            return sortedValues.find((_, i) => (r -= (i + 1) / sum) <= 0);
        };
    },
    getRandomValue = random([6, 7, 8, 9, 10]),
    counts = {};

for (let i = 0; i < 1e6; i++) {
    let value = getRandomValue();
    counts[value] = (counts[value] || 0) + 1;
}

console.log(counts);
.as-console-wrapper { max-height: 100% !important; top: 0; }
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
  • Shouldn't it be `probabilities = numbers.map((v, i) => (i+1) / sum)`? Assuming you are linearly increasing the probability based on the position in the sorted array. – adiga Aug 19 '20 at 08:36
  • @adiga, yes it should be. (but is the same...) – Nina Scholz Aug 19 '20 at 08:37
  • How can I use these probabilities when for example array [16, 2, 5, 10]? Four item but the biggest one is in index 0. – Zagano Aug 19 '20 at 08:41
  • right, I thought `numbers` was going to be the input array and you were picking based on the value of the input array – adiga Aug 19 '20 at 08:42
  • @Zagano, you need a sorted array, in this case. – Nina Scholz Aug 19 '20 at 08:42
  • @NinaScholz I sorted array and use it for `numbers`. There are possibilities but I cannot choose random items according to these probabilities. Sorry for this simple problem – Zagano Aug 19 '20 at 08:50
  • i don't understand. – Nina Scholz Aug 19 '20 at 08:52
  • @NinaScholz How can i choose random item for such array `arr3 = [1,2,7,8,9];` according to your probabilities. I'm not sure I understand your code. – Zagano Aug 19 '20 at 09:00
  • i changed it a little bit without calculating the probabilities in advance. no it uses the array of the values and takes the index with an adjustment. – Nina Scholz Aug 19 '20 at 09:12