arrays - 确定从 n 个数组中选择 1 个唯一元素的可能性的算法

Question

有一点坚果要破解。我有算法的蛮力实现，这并不难，但显然我想要更有效的东西。

问题如下：

想象一下，您有n 个数组，每个数组都填充了一些介于1和n之间的值。我需要确定是否可以从这些数组中的每一个中选择一个元素，以便我从1到n中选择每个元素恰好一次。一个小例子：假设n = 4我们有这些n数组：

[1,2,3,4]
[1,3]
[2,4]
[3,4]

这种数组组合将通过算法，因为可以（例如）分别从每个数组中选择 1、3、2、4。另一种可能性是 2、1、4、3。一个反例是：

[1,2,3]
[3]
[3,4]
[3,4]

在这里，您清楚地看到这些输入数组不会通过算法。不可能以每个元素被选择一次的方式从每个数组中选择 1 个元素。

正如我所说，蛮力方法并没有那么复杂，但我想要更有效的方法，而不需要遍历所有可能的排列，直到找到符合标准的排列。

标签： arraysalgorithm

Answer 1

这个问题可以简化为最大二分匹配，可以通过Ford-Fulkerson Algorithm for Maximum Flow Problem 解决：

让我们创建一个节点流图，2*n第一组n节点表示数组，而下一组n节点表示值。因此，当且仅当数组内部包含值时，从i第一个集合中的节点到第二个集合中的节点会有一条边。此边的容量应为 1，表示您只能从每个数组中选择一个。jij

形成此图后，应用经典算法找到答案。

对于问题中的示例：

[1,2,3,4]
[1,3]
[2,4]
[3,4]

我们可以形成这个图

白色节点代表数组，而绿色节点代表值。