algorithm - 伪代码算法，用于计算从 N 个不等向量中选择的 N 个值的所有排列而不重复

Question

这个问题是针对我正在尝试编写的程序，该程序涉及将物理部件链连接在一起。我相信我已经将其提炼为最简单的问题形式。如果有人知道描述此问题的任何其他词，我也将不胜感激，因为大约 30 分钟的相关问题搜索甚至没有找到此问题的名称。

你有 N 个向量。如果您从每个向量中选择一个值并且不允许任何重复，您将得到我要查找的类型的一种排列。什么是无需暴力破解即可找到所有这些的伪代码算法？

例子:
你有载体

v1=[1 2]   v2=[1 2 3]   v3=[1 2 3 4]  

(编辑说明:向量的嵌套是无意的，不能在算法中加以利用。) 您从每个向量中选择值并且不允许重复。

Value 1 is from v1 ---> 2
Value 2 is from v2 ---> 1   
Value 3 is from v3 ---> 4

Resulting permutation is [2 1 4].

这是一个允许的排列。这是一个不允许排列的示例，因为它会重复。

Value 1 is from v1 ---> 2
Value 2 is from v2 ---> 1
Value 3 is from v3 ---> 2    

Resulting permutation is [2 1 2], which is invalid due to repeats.

找到所有有效排列的算法是什么？

如果你能在计算之前计算出有多少排列，则加分。

如果我能在其他人之前想出答案，我一定会回复。

Answer 1

您给出的示例具有嵌套向量，这意味着 v_i 中的条目是 v_{i+1} 中条目的子集。如果这确实是您应用程序的一般情况，那么解决方案的数量很简单:

n_1 * (n_2 - 1) * ... * (n_k - (k-1))

其中n_i是v_i的长度，有k个嵌套向量。

就算法而言，如果您想生成所有可能的解决方案，那么我认为没有比在消除已选择的条目后从每个连续的向量中进行选择更好的方法了。

如果您没有嵌套，可视化此问题的一个好方法是 Marriage Problem在以下意义上。使k个顶点对应给定的k个向量

v_1  v_2 ...  v_k

和另一个 m 个顶点对应于组合向量的不同条目

a_1 a_2 ... a_m

当且仅当 a_i 出现在 v_j 中时，然后将 a_i 连接到 v_j。目标是找到一个 maximum matching在 v 和 a 之间接触所有 v。也就是说，选择 k 条边，使每条 v_i 恰好是一条边的端点。

任何标准算法，例如使用增强路径，将努力找到一个解决方案或生成所有解决方案。