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

就在这里。我在这个德国论坛上提问并得到以下答案：问题可以简化为在二分图上找到最大匹配。为了做到这一点，为多重集中的所有元素引入顶点。这些顶点形成二分图的一侧。然后，为每个限制集引入顶点。这些顶点形成二分图的另一边。现在将每个限制集的边引入到第一侧的那些顶点，使得第一侧的顶点被“命中”当且仅当它表示包含在连接集中的元素。

您的示例的二分图如下所示：

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

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