permutation - 生成有限制的随机多集排列

Question

是否有任何已知的算法如何有效地生成具有附加限制的任何随机多集排列。

例子:
我有多个项目，例如:{1,1,1,2,2,3,3,3} ，以及一组限制性的集合，例如 { {3} , {1,2} , {1,2,3} , {1,2,3} , {1,2,3} , {1,2,3} , {2,3} , {2,3} }.我正在寻找项目的排列，但第一个元素必须是 3，第二个元素必须是 1 或 2，等等。

一种符合限制的排列是:{3,1,1,1,2,2,3,3}

Answer 1

就在这里。我问了 this German forum并得到以下答案:问题可以简化为查找 a maximum matching on a bipartite graph .
为此，请为多重集中的所有元素引入顶点。这些顶点形成二部图的一侧。然后，为每个限制集引入顶点。这些顶点形成二部图的另一侧。现在将每个限制集中的边引入第一边的顶点，使得第一边的顶点“命中”当且仅当它表示包含在连接集中的元素。

您示例的二部图如下所示:


现在匹配以不选择任何两条相邻边的方式选择边。例如。为第二个限制“{1,2}”选择第一个“1”，然后它不能再用于任何其他限制，因为使用来自该顶点的另一条边将不再导致匹配。

如果您对此有其他问题，请随时提问。