全排列

renxiaobin32132

全排列算法的遞歸與非遞歸實現(xiàn).出于語言特性問題,運行效率較低.
P(i-1) (1  P(i+2) > . > Pn
  即使進行了Pi和Pj的交換,這仍然是這一部分最大的一個排列。將此排列逆序倒置(變成最小的排列)即為所求的下一個排列.
5.重復(fù)步驟1-4,直到步驟1中找不到“不符合趨勢”的數(shù)字.
*/
// 參數(shù)arr:待進行全排列的數(shù)組(沒有重復(fù)的元素)
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 ;  // 找不到"不符合趨勢"的數(shù)字,說明所有的排列已經(jīng)找到
}
/**/ /*
var ar = Combin("f4e3r21".split(""));
for(var i=0;i
1、首先看最后兩個數(shù)4, 5。 它們的全排列為4 5和5 4, 即以4開頭的5的全排列和以5開頭的4的全排列。
由于一個數(shù)的全排列就是其本身，從而得到以上結(jié)果。
2、再看后三個數(shù)3, 4, 5。它們的全排列為3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六組數(shù)。
即以3開頭的和4,5的全排列的組合、以4開頭的和3,5的全排列的組合和以5開頭的和3,4的全排列的組合.
從而可以推斷，設(shè)一組數(shù)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。
為了更容易理解，將整組數(shù)中的所有的數(shù)分別與第一個數(shù)交換，這樣就總是在處理后n-1個數(shù)的全排列。
               
               
               

本文來自ChinaUnix博客，如果查看原文請點：http://blog.chinaunix.net/u3/107452/showart_2113347.html