我必须找到满足某些规则的 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]。此外，还定义了用于派生规则的全局二维数组"模式"。这个数组可以看作是一个大的 0-1 矩阵，有 n 行和 19 列)
n!远不及多项式， 所以你的执行时间会 随着n的增大而急剧增加。 如果有一些模式"哪些号码可以/不能去 到哪个插槽"，然后您可以通过以下方式改进算法 使用结构，但你的问题听起来不响 所以。
可能有一些帮助。首先，迭代 在要放置的数字上 - 而不是要填写的插槽：
对于1, .., n的每个数字，请使用链接 他们可以进入的插槽列表。例如。数字 3 只能 进入插槽 3、16、7、6 --这是 n=3 的链表。
维护所有n元素的"中央"数组(直接访问)。 每当你把一个数字，比如x，到插槽p，你就会 反转该中心数组的第 p 个元素。
对n数字进行排序，以便在 列表是可以进入最少插槽数的数字， 在底部可以进入最多数量的那个 的插槽。
从列表顶部的数字开始，然后继续服用 使用这些链表的排列 - 将数字放置到 未填满的插槽。这为您提供了最佳解决方案，但 指数时间。问题是指数级的。
您还可以使用子优化算法在多项式时间内运行，但不一定允许所有排列。