全排列

renxiaobin32132

全排列算法的递归与非递归实现.出于语言特性问题,运行效率较低.
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