有n个孩子和一组有限的可分辨玩具；
每个孩子都喜欢所有玩具中的一个子集；
每个孩子都需要拥有一个确切的玩具数量ti有些玩具不止一个孩子喜欢。
一个玩具不能由多个孩子拥有
.
可能有很多方法可以满足每个孩子对玩具的需求。
问题：给定n，{ti}，{ti}和种子rng，从所有可能的儿童玩具配置中，我需要选择一个均匀分布（或至少接近均匀分布）的配置，即从儿童到他们拥有的玩具的映射。
生成所有可能的配置并选择j-th是不可能的-可能有很多这样的配置。
在下面的例子中有4个孩子：红色，蓝色，绿色和黄色。红色需要拥有4个玩具，蓝色-5，绿色-3，黄色-3。孩子们喜欢的玩具在相应颜色的长方形里。
因此，我需要的要么是生成一个分布良好的Map<Child, Set<Toy>>算法的概要，要么是任何有助于阅读以解决问题的链接。
最佳答案
准备一个二分图如下对于每个子i，创建t_i顶点对于每个玩具，创建一个顶点。每当孩子喜欢玩具时，将所有的顶点连接到其顶点。给孩子的玩具的有效分配对应于图中的完美匹配使用您喜欢的匹配算法（例如Hopcroft--Karp）计算一个赋值，然后根据需要运行Jerrum and Sinclair的markov链。
关于algorithm - 生成在 child 中分发玩具的多种方法之一，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25751914/