1

这个问题是针对我正在尝试编写的一个程序，该程序涉及将物理部件链连接在一起。我相信我已将其提炼成最简单的问题形式。如果有人知道描述此问题的任何其他词，我也将不胜感激，因为搜索相关问题的大约 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.

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

如果您可以在计算之前计算出有多少排列，则可以加分。

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

4

2 回答 2

4

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

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

其中n_i是长度，v_i并且有k嵌套向量。

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

如果您没有嵌套，则可视化此问题的一种好方法是在以下意义上将其视为婚姻问题。制作与给定向量k对应的顶点k

v_1  v_2 ...  v_k

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

a_1 a_2 ... a_m

然后连接a_i当v_j且仅当a_i出现在 中v_j。目标是在s 和接触所有 s 的 s之间找到最大匹配。也就是说，选择边以使每个边都恰好是一条边的端点。vavkv_i

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

于 2012-09-11T05:05:42.240 回答
1

我认为你可以逐步解决这个问题。设 s1, s2, s3,..,sk 是涉及 v1, v2, .., vn 的解。现在对于每个当前解决方案 si 和元素 j（vn+1 中的 j）使用 vn+1，查看 j 是否已经在 si 中，如果没有，则将其添加到您的新集合中（对应于 n+1）。

  1. 为 v1 中的 j 初始化 S={ {j} }
  2. 对于 n=2..m：
    1. 新 = {}
    2. 对于 vn 中的 j
      1. 对于 s 在 S
        1. 如果 j 不在 s 中，则将 sU{j} 添加到 newS S = newS
  3. 返回 S
于 2012-09-11T05:07:31.797 回答