algorithm - 20个元素的排列，满足一定的规则

Question

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

这是我现在正在使用的(Pascal 代码):

 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大矩阵)

Answer 1

n! 远不是多项式，所以你的执行时间会随着 n 变大，它会急剧增加。如果在“哪些数字可以/不可以去”上有某种模式到哪个插槽”，那么您可以通过以下方式改进算法使用它的结构，但你的问题听起来不对所以。

可能会有一些帮助。首先，迭代关于要放置的数字——而不是要填写的位置:

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

维护所有 n 元素的“中央”数组(直接访问)。每当你放置一个数字，比如 x，到槽 p，你会反转该中央数组的第 p 个元素。

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

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

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