匹配两个集合的元素的方法

Question

考虑这个问题：

有两组，每组 N 个元素，1 <= N <= 21. I need to pair each element from set #1 to a distinct element of set #2 with restrictions. Input also contains a matrix where the value at row i, column j is 1 if the ith element of set #1 can be matched with the jth element of set #2. If it can't be matched the value is 0. Find how many ways there are to make the N pairs of elements mod 10^9+7.

输入示例（第一行是 N，接下来的 N 行是矩阵，每行一行）

3
0 1 1
1 1 1
1 1 1

输出示例

4

输入示例：

3
1 1 1
1 1 1
1 1 1

输出示例：

6

我不知道从哪里开始。尝试所有可能的匹配订单将花费很长时间，而且我可能会耗尽内存。我认为这可能是动态规划。怎么解决这个问题？

Answer 1

您可以将其表述为分配问题，这是一种线性规划 (LP)，可以使用通用 LP 包（例如，使用单纯形法）或使用专门设计用于解决分配问题的软件包来解决.

定义两组元素的集合

令

S1

和

S2

分别等于第 1 组和第 2 组中的元素集合。

从给定的包含零和一的矩阵定义可行映射集

令

J(i)

为 S1 中的元素 i 可以映射到的 S2 中的元素集合。

令

I(j)

为 S1 中可以映射到 S2 中元素 j 的元素集合。

定义二进制值变量

如果S1中的成员i映射到S2中的成员j，则Xij等于1；否则等于零

定义约束

S1 中的每个 i 必须恰好映射到 S2 中的 1 个元素

SUM(S2 中的 j) 对于 S1 中的每个 i，Xij = 1

S2 中的每个 j 必须恰好映射到 S1 中的 1 个元素

SUM(S1 中的 i) 对于 S2 中的每个 j，Xij = 1

无需定义要最小化或最大化的目标函数，因为只需要可行的解决方案。