2

我必须找到满足某些规则的 20 个元素的所有可能排列。例如，元素 1 永远不能位于位置 3、4、6、7、8、12 和 17，元素 2 永远不能位于位置 1、2、7、10、19 等等。目前，我正在使用一个递归函数，该函数遍历所有可能的排列并检查规则是否得到满足。这适用于 10 个元素（10 个！排列），但正如您可以想象的那样，该算法不再适用于 20 个元素。有谁知道跳过不需要的排列的更有效的方法？（我假设，从 20！=2.4E18 可能的排列中，只有 1-2 Mio。将满足规则。

这就是我现在使用的（帕斯卡代码）：

 procedure permu(p:feldtyp; ka:bereich); 
 var
   i,h : bereich; 
 label skip;
 begin 
   if ka=teams then begin 

    //execute certain tests, skip the output part if the tests fail 
    for i:=1 to ka do if ((hh11[P[i]]+hh21[i])<>(ka-1)) or 
      ((patterns[h1[P[i]]][teams-1]=patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][1])=(patterns[h2[i]][teams-1]=patterns[h2[i]][1]))) or 
      ((patterns[h1[P[i]]][teams-1]<>patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][1])<>(patterns[h2[i]][teams-1]=patterns[h2[i]][1]))) or 
      ((patterns[h1[P[i]]][teams-1]<>patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][1]) and (patterns[h2[i]][teams-1]=patterns[h2[i]][1]))) or 
      ((patterns[h1[P[i]]][teams-1]=patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-2]=patterns[h1[P[i]]][teams-3]) or (patterns[h2[i]][2]=patterns[h2[i]][3]))) or 
      ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][teams-2]) and (patterns[h2[i]][1]=patterns[h2[i]][2])) 
    then goto skip; 

    //all tests passed, write permutation
    // ...
    skip:
  end 
  else begin 
    for i := ka to teams do begin 
      h := P[i]; 
      P[i] := p[ka]; 
      P[ka] := h; 
      permu(p, ka+1); 
    end;
  end;
end;

（“teams”是常数 20，“h1”、“h2”是在其他地方定义的一些数组 [1..20]。此外，定义了一个全局二维数组“patterns”，用于导出规则。这个数组可以看成一个n行19列的大0-1矩阵）

4

1 回答 1

0

n!远不接近多项式，因此您的执行时间将随着时间的推移而急剧n增加。如果在“哪些数字可以/不能去哪个插槽”上有某种模式，那么你可以通过使用它的结构来改进算法，但你的问题听起来不是这样。

可能有一些帮助。首先，迭代要放置的数字 - 而不是要填充的插槽：

对于每个数字1, .., n，使用它们可以进入的插槽的链接列表。例如。数字 3 只能进入插槽 3、16、7、6——这就是 n=3 的链表。

维护所有n元素的“中央”数组（直接访问）。每当您将一个数字（例如 x）放入插槽 p 时，您都会反转该中央数组的第 p 个元素。

对您的数字进行排序n，以便列表顶部是可以进入最少插槽数的数字，而底部是可以进入最多插槽数的数字。

从列表顶部的数字开始，并继续使用这些链接列表进行排列——将数字放置到未填充的插槽中。这为您提供了最佳但指数时间的解决方案。问题是指数级的。

您还可以使用子优化算法在多项式时间内运行，但不一定允许所有排列。

于 2012-11-23T04:31:48.307 回答