免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1537 | 回复: 0

全排列 [复制链接]

论坛徽章:
0
发表于 2009-12-07 22:10 |显示全部楼层
全排列算法的递归与非递归实现.出于语言特性问题,运行效率较低.
P(i-1) (1  P(i+2) > . > Pn
  即使进行了Pi和Pj的交换,这仍然是这一部分最大的一个排列。将此排列逆序倒置(变成最小的排列)即为所求的下一个排列.
5.重复步骤1-4,直到步骤1中找不到“不符合趋势”的数字.
*/
// 参数arr:待进行全排列的数组(没有重复的元素)
function  Combin(arr) {
     var  arResult  =  [];
     var  ar  =  arr.sort();
    arResult.push(ar);
     for (;;) {
        ar  =  FindNext(arResult[ 0 ],ar);
         if ( ! ar)  return  arResult;
        arResult.push(ar);
    }
}
function  FindNext(arFirst,arLast) {
     for ( var  i = arLast.length - 1 ;i > 0 ;i -- ) {
         if (arLast[i - 1 ]  =   0  )  break ;
            }
            ar[i  +  idx]  =  ar[i - 1 ];
            ar[i - 1 ]  =  ch;
             return  ar.slice( 0 ,i).concat(ar.slice(i).reverse());
        }
    }
     return   null ;  // 找不到"不符合趋势"的数字,说明所有的排列已经找到
}
/**/ /*
var ar = Combin("f4e3r21".split(""));
for(var i=0;i
1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。
由于一个数的全排列就是其本身,从而得到以上结果。
2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。
即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.
从而可以推断,设一组数p = {r1, r2, r3, ... ,rn}, 全排列为perm(p),pn = p - {rn}。
因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), ... , rnperm(pn)。当n = 1时perm(p} = r1。
为了更容易理解,将整组数中的所有的数分别与第一个数交换,这样就总是在处理后n-1个数的全排列。
               
               
               

本文来自ChinaUnix博客,如果查看原文请点:http://blog.chinaunix.net/u3/107452/showart_2113347.html
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP