1
$\begingroup$

I have an array of items $A = \{A_i\}, i \in I $ with integer weights $W_i, i \in I$. I need to build a function $f: I \rightarrow A $, that produces evenly distributed patterns of array elements predictable manner.

For example: an array of 3 elements: $A_1 = 1, A_2 = 2, A_3 = 3$ and weights: $W_1 = 1, W_2 = 2, W_3 = 2$. This means that pattern will consist of 5 repeating elements. One example of this pattern: $1, 2, 3, 2, 3, 1, 2, 3, 2, 3, 1$ (each iteration of 5 elements has exactly one 1, two 2's and two 3's).

What I need is the name of this problem to search for suitable algorithms. Thank you!

$\endgroup$
0
$\begingroup$

Normalize $W$ by calculating the greatest common divisor of $W$ and dividing every element by it.

Then just repeatedly iterate over $W$ in order, and if $W_i > 0$ subtract $1$ from it and output $A_i$. You stop when all $W_i = 0$.

If $1, 2, 2, 3, 3, 1, 2, 2, 3, 3, \dots $ in your example is also fine then just output $W_i$ copies of $A_i$ after normalization.

$\endgroup$
0
$\begingroup$

The name of this problem is weighted sampling without replacement. One can search the web or stackoverflow. Not much result on this site yet.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.