Return random item by its weight, advanced level

Question

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

Imagine more advanced problem.

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?

Answer 1

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   |

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