我必须找到满足特定规则的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。此外,还定义了用于导出规则的全局二维数组“模式”。这个数组可以看作是一个n行19列的大0-1矩阵)
发布于 2012-11-23 12:31:48
n!不是多项式的,所以当n更大时,你的执行时间会急剧增加。如果有一些关于“哪个数字可以/不可以去哪个插槽”的模式,那么你可以通过使用它的结构来改进算法,但你的问题听起来不是这样的。
这可能会有一些帮助。首先,迭代要放置的数字--而不是要填充的空位:
对于每个编号1, .., n,使用它们可以进入的插槽的链接列表。例如:数字3只能放入插槽3、16、7、6--这是n=3的链表。
维护所有n元素的“中央”数组(直接访问)。每当你把一个数字,比如x,放到槽p上,你就会反转那个中心数组的第p个元素。
对您的n编号进行排序,以便在列表的顶部是可以放入最少插槽的编号,在底部是可以放入最多插槽的编号。
从列表顶部的数字开始,继续使用这些链表进行排列--将数字放入未填充的空位。这为您提供了在最佳但指数时间内的解决方案。这个问题是指数型的。
您还可以使用子优化算法在多项式时间内运行,但不一定允许所有的排列。
https://stackoverflow.com/questions/13489395
复制相似问题