The initial two-dimensional array contains n elements. The array looks like this:

var all = [ ["value", 1], ["value2", 0.9], ["value3", 2.2] ];

We need to generate a new array, whose length = k . Provided that n> = k.

  1. A new array should consist of elements of the original array (no repetitions).
  2. The length of the new array is less than or equal to the length of the original.
  3. Elements in the new array do not preserve the order of the original array (mixed together).

In a good way, we just need to shuffle the source array and cut off k elements from it. But this is not all the conditions. Pay attention to the second values ​​of each element of the array: 1, 0.9, 2.2 ... These are the coefficients that determine the probability that this element will fall into a new array. This is any non-negative number, including 0. If 0, the element should not fall into the new array only if we do not have a "shortage" of elements. Suppose we have 100 elements in the original array, and there should be only 50 elements in the new array. It turns out that each specific element will fall into a new array with a probability of 0.5. This is the default probability that we must consider. Moreover, say, the coefficient of this particular element = 2.3, and this should mean that this element should get into a new array 2.3 times more likely than, say, an element for which this coefficient would be equal to one.

If all elements had coefficients equal to one, they would all be equal and equally often fall into the new array.

Accordingly, if the coefficient is <1, then the element will fall into the new array with a lower probability. It should be emphasized that if there are 2 elements nearby, whose coefficients are equal to 0.001 and 1000, respectively, then both of these elements can get into a new array. We have no bias, only chance.

I sketched the code. It can also help to understand the requirements for the algorithm. However, the complexity of my algorithm is extremely high. The algorithm is irrational. Please help with optimization ideas.

http://jsfiddle.net/s9gf2z4g/3/

    1 answer 1

    Sum up the probabilities. We generate a random number 0 <= x <sum. We go through the array (better in the list), while the sum of the passed elements is less than the generated random value. Add to the result list the corresponding element of the source, and from the source - delete. Repeat the cycle, reducing the amount, of course, by the weight of the excluded element.

    JavaScript, I do not know, here is the code on Python, it reads almost like this text in English.

     import random src = [ ("value", 1), ("value2", 0.9), ("value3", 2.2) ]; dst = [] while (len(dst) < 2): r = random.random() * sum(i[1] for i in src) s = 0 x = len(src) - 1 for i in range(len(src)): s += src[i][1] if s >= r: x = i break dst.append(src[x][0]) del src[x] print(src) print(dst)