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 个元素。

正如我所说，蛮力方法并没有那么复杂，但我想要更高效的方法，在我找到满足标准的排列之前不经过所有可能的排列。

Answer 1

这个问题可以简化为 Maximum Bipartite Matching , 这可以通过 Ford-Fulkerson Algorithm for Maximum Flow Problem 来解决:

让我们创建一个 2*n 节点的流程图，第一组 n 节点代表数组，而下一组 n code> 节点代表值。因此，当且仅当在数组 i 中时，从第一组中的节点 i 到第二组中的节点 j 会有一条边，有包含值 j。这条边的容量应该是1，代表每个数组只能选一个。

形成这个图后，应用经典算法求答案。

对于问题中的例子:

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

我们可以形成这个图

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