首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >20个元素的排列,满足一定的规则

20个元素的排列,满足一定的规则
EN

Stack Overflow用户
提问于 2012-11-21 16:46:07
回答 1查看 678关注 0票数 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。都会满足规则。

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

代码语言:javascript
复制
 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矩阵)

EN

回答 1

Stack Overflow用户

发布于 2012-11-23 12:31:48

n!不是多项式的,所以当n更大时,你的执行时间会急剧增加。如果有一些关于“哪个数字可以/不可以去哪个插槽”的模式,那么你可以通过使用它的结构来改进算法,但你的问题听起来不是这样的。

这可能会有一些帮助。首先,迭代要放置的数字--而不是要填充的空位:

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

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

对您的n编号进行排序,以便在列表的顶部是可以放入最少插槽的编号,在底部是可以放入最多插槽的编号。

从列表顶部的数字开始,继续使用这些链表进行排列--将数字放入未填充的空位。这为您提供了在最佳但指数时间内的解决方案。这个问题是指数型的。

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

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/13489395

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档