# Return random item by its weight, advanced level

There are many typical questions like Return random `list` item by its `weight`

You have N sources of pair `(item_id, weight)` information. Let's call them Shards. Shards contain lists of pairs `(item_id, weight)`.

And you have central node, let's call it Central.

The problem is: on Central choose random item from The Big List (the list virtually merged from all lists on all shards) according to their weight through all weights.

For example, we have two shards:

``````+-------+---------+--------+
| shard | item_id | weight |
+-------+---------+--------+
|   1   |     1   |    7   |
|   1   |     2   |    4   |
|   1   |     3   |    2   |
|   2   |     4   |    5   |
|   2   |     5   |    1   |
+-------+---------+--------+
``````

(Let `item_id` will be unique through all shards.)

First problem:

How to choose `item_id` randomly but weighted through all shards? I.e. `total_weight == 7+4+2+5+1 == 19`, so `1` will be chosen with probability of 7/19, `2` - 4/19, `3` - 2/19 and so on.

Second problem:

How to range all items from all shards randomly, but weighted through all shards?

I.e. ideal ranging will be: `1, 4, 2, 3, 5` (according to their weights),

but there may be another ranging like `1, 2, 4, 3, 5`, but slightly less frequently than previous,

...

and worst case `5, 3, 2, 4, 1` can also appear, but with very-very little probability.

Is there common problem in computer science for this?

• What do you mean by your second problem? The sum of the weights for the items from a shard should indicate how likely it is that an item from that shard gets chosen. If the weight distribution over the shards is really skewed, then the shard selection will be anything but random, while the item selection still is. Sep 6, 2016 at 11:12

In problem 1, you do not use the information to which shard a certain item belongs. So this is actually just choosing an item randomly with weights. You can use the method in the post you linked to.

For problem 2 I think you could repeatedly apply problem 1. First you choose the first item and then you recalculate your list and weightings. This can be done smartly by for example substracting the weight of the item you choose first from the total weight. Then repeat for the second item, etc...

More concrete, suppose you apply problem 1 once, and it chooses 4 weightedly at random. Then you would apply problem 1 again on:

``````+---------+--------+

| item_id | weight |

+---------+--------+

|     1   |    7   |

|     2   |    4   |

|     3   |    2   |

|     5   |    1   |

+---------+--------+
``````