Imagine you have a list of objects. Each object looks like:

{'itemName':'name',
 'totalItemAppearance':100,
 'appearancePerList': 20}

and some number X which stands for number of lists that can contain such items.

What i need to do is randomly picking an item put them into lists with respecting item parameters.

In the end I expect X number of lists whit item which is used(in all lists) exactly 'totalItemAppearance' times but in each list it should be less or equal than 'appearancePerList'

It looks simple but i don't know how to build an algorithm properly and I can't classify the type of "distribution problem" I need for this issue so i could properly ask Google. Thank you for replies!

CodePudding user response：

First of all, you need not consider all different types of objects at the same time: There are no relations between different kinds of objects. So I will only consider the case where there is only one type of object.

What you want to do is to pick a uniform random sample from a set of objects satisfying some condition. The objects here are all possible distributions of the objects to the lists, and the condition is that the total number of objects should be 'totalItemAppearance' and that no list contains more than 'appearancePerList' objects.

If 'appearancePerList' is not too small then you can apply the following algorithm (and not wait for an eternity):

--> Pick a uniform random distribution of 'totalItemAppearance' items to lists (much easier to do)

--> If there are at most 'appearancePerList' objects in each list accept

--> Otherwise repeat

This algorithm will produce the uniform samples you wanted. I do not know if this sampling technique has a name (maybe a special case of rejection sampling?).