< script?language = " JavaScript " >
<!--
// 全排列遞歸算法
// code?by?meixx(梅雪香)
/**/ /*
遞歸的算法采用分而治之的思想?
考慮序列?P1P2P3Pn?可以分解為?P1?+?C(P2P3Pn),依此類推.
*/
function ?combination(arr) {
???? var ?len? = ?arr.length;
???? if (len? == ? 2 ) {
???????? var ?a? = ?arr[ 0 ],?b? = ?arr[ 1 ];
???????? return ?[a + b,b + a];
????}
???? else ? if (len? == ? 1 )?? return ?arr;
???? else {
???????? var ?strRtn? = ? "" ;
???????? for ( var ?i = 0 ;i < len;i ++ ) {
????????????strRtn? += ?merge(arr[i],combination(arr.slice( 0 ,i).concat(arr.slice(i + 1 ,len)))).join( " , " ) + " , " ;
????????}
???????? return ?strRtn.replace( / \,$ / , "" ).split( " , " );
????}
}
function ?merge(head,arr) {
???? for ( var ?i = 0 ;i < arr.length;i ++ )
????????arr[i]? = ?head? + ?arr[i];
???? return ?arr;
}
/**/ /*
var?ar?=?combination("54321".split(""));
for(var?i=0;i<ar.length;i++)
????document.write(ar[i].join(""),"<br>");
*/
// -->
</ script >
< script?language = " JavaScript " >
<!--
// 全排列非遞歸算法
// code?by?meixx(梅雪香)
/**/ /*
非遞歸全排列算法的基本思想是:
????1.找到所有排列中最小的一個(gè)排列P.
????2.找到剛剛好比P大比其它都小的排列Q,
????3.循環(huán)執(zhí)行第二步,直到找到一個(gè)最大的排列,算法結(jié)束.
下面用數(shù)學(xué)的方法描述:
給定已知序列?P?=??A1A2A3An?(?Ai!=Aj?,?(1<=i<=n??,?1<=j<=n,?i?!=?j??)?)
找到P的一個(gè)最小排列Pmin?=?P1P2P3Pn??有??Pi?>?P(i-1)?(1?<?i?<=?n)
從Pmin開始,總是目前得到的最大的排列為輸入,得到下一個(gè)排列.
方法為:
1.從低位到高位（從后向前），找出“不符合趨勢(shì)”的數(shù)字。即找到一個(gè)Pi，使Pi?<?P(i+1)。
??若找不到這樣的pi，說(shuō)明我們已經(jīng)找到最后一個(gè)全排列，可以返回了。
2.在?P(i+1)P(i+2)Pn?中,找到一個(gè)Pj,便得?Pj"剛剛好大于"Pi.?
??("剛剛好大于"的意思是:在?P(i+1)P(i+2)Pn?中所有大于Pi的元素構(gòu)成的集合中最小的元素.)
3.交換?Pi?,?Pj?的位置.注意:此處不改變i和j的值,改變的是Pi和Pj.
4.交換后，?P1P2P3Pn??并不是準(zhǔn)確的后一個(gè)排列。因?yàn)楦鶕?jù)第1步的查找，我們有P(i+1)?>?P(i+2)?>?.?>?Pn
??即使進(jìn)行了Pi和Pj的交換,這仍然是這一部分最大的一個(gè)排列。將此排列逆序倒置(變成最小的排列)即為所求的下一個(gè)排列.
5.重復(fù)步驟1-4,直到步驟1中找不到“不符合趨勢(shì)”的數(shù)字.
*/
// 參數(shù)arr:待進(jìn)行全排列的數(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 ]? < ?arLast[i]) {? // 找到了"不符合趨勢(shì)"的數(shù)字
???????????? var ?ar? = ?arLast.slice();
???????????? var ?strTail? = ?ar.slice(i).join( "" );
???????????? var ?tmpStr? = ?arFirst.join( "" );
???????????? var ?strSearch? = ?tmpStr.substr(?tmpStr.indexOf(ar[i - 1 ])? + ? 1 ?);
???????????? // 確定ar[i-1]要交換的字符及該字符的位置
???????????? for ( var ?j = 0 ,k = strSearch.length;j < k;j ++ ) {
???????????????? var ?ch? = ?strSearch.charAt(j);
???????????????? var ?idx? = ?strTail.indexOf(ch);
???????????????? if (?idx? >= ? 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ì)"的數(shù)字,說(shuō)明所有的排列已經(jīng)找到
}
/**/ /*
var?ar?=?Combin("f4e3r21".split(""));
for(var?i=0;i<ar.length;i++)
????document.write(ar[i].join(""),"<br>");
*/
// -->
</ script >