快捷導(dǎo)航

JavaScript全排列的六種算法具體實(shí)現(xiàn)

更新時(shí)間：2013年06月29日 16:09:26 作者：

這篇文章介紹了全排列的六種算法有，交換算法，鏈接算法，回溯算法等，有需要的朋友可以參考一下

全排列是一種時(shí)間復(fù)雜度為：O(n!)的算法，前兩天給學(xué)生講課，無意間想到這個(gè)問題，回來總結(jié)了一下，可以由7種算法求解，其中動(dòng)態(tài)循環(huán)類似回溯算法，實(shí)現(xiàn)起來比較繁瑣，故總結(jié)了6種，以饗讀者。所有算法均使用JavaScript編寫，可直接運(yùn)行。
算法一：交換（遞歸）

復(fù)制代碼代碼如下:

<html xmlns="http://www.w3.org/1999/xhtml">  
<head>  
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />  
    <title>Full Permutation(Recursive Swap) - Mengliao Software</title>  
</head>  
<body>  
<p>Full Permutation(Recursive Swap)<br />  
Mengliao Software Studio - Bosun Network Co., Ltd.<br />  
2011.05.24</p>  
<script type="text/javascript">  
/*  
全排列（遞歸交換）算法  
1、將第一個(gè)位置分別放置各個(gè)不同的元素；  
2、對剩余的位置進(jìn)行全排列（遞歸）；  
3、遞歸出口為只對一個(gè)元素進(jìn)行全排列。  
*/ 
function swap(arr,i,j) {  
    if(i!=j) {  
        var temp=arr[i];  
        arr[i]=arr[j];  
        arr[j]=temp;  
    }  
}  
var count=0;  
function show(arr) {  
    document.write("P<sub>"+ ++count+"</sub>: "+arr+"<br />");  
}  
function perm(arr) {  
    (function fn(n) { //為第n個(gè)位置選擇元素  
        for(var i=n;i<arr.length;i++) {  
            swap(arr,i,n);  
            if(n+1<arr.length-1) //判斷數(shù)組中剩余的待全排列的元素是否大于1個(gè)  
                fn(n+1); //從第n+1個(gè)下標(biāo)進(jìn)行全排列  
            else 
                show(arr); //顯示一組結(jié)果  
            swap(arr,i,n);  
        }  
    })(0);  
}  
perm(["e1","e2","e3","e4"]);  
</script>  
</body>  
</html> 

算法二：鏈接（遞歸）

復(fù)制代碼代碼如下:

<html xmlns="http://www.w3.org/1999/xhtml">  
<head>  
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />  
    <title>Full Permutation(Recursive Link) - Mengliao Software</title>  
</head>  
<body>  
<p>Full Permutation(Recursive Link)<br />  
Mengliao Software Studio - Bosun Network Co., Ltd.<br />  
2012.03.29</p>  
<script type="text/javascript">  
/*  
全排列（遞歸鏈接）算法  
1、設(shè)定源數(shù)組為輸入數(shù)組，結(jié)果數(shù)組存放排列結(jié)果（初始化為空數(shù)組）；  
2、逐一將源數(shù)組的每個(gè)元素鏈接到結(jié)果數(shù)組中（生成新數(shù)組對象）；  
3、從原數(shù)組中刪除被鏈接的元素（生成新數(shù)組對象）；  
4、將新的源數(shù)組和結(jié)果數(shù)組作為參數(shù)遞歸調(diào)用步驟2、3，直到源數(shù)組為空，則輸出一個(gè)排列。  
*/ 
var count=0;  
function show(arr) {  
    document.write("P<sub>"+ ++count+"</sub>: "+arr+"<br />");  
}  
function perm(arr) {  
    (function fn(source, result) {  
        if (source.length == 0)  
            show(result);  
        else 
            for (var i = 0; i < source.length; i++)  
                fn(source.slice(0, i).concat(source.slice(i + 1)), result.concat(source[i]));  
    })(arr, []);  
}  
perm(["e1", "e2", "e3", "e4"]);  
</script>  
</body>  
</html> 

算法三：回溯（遞歸）

復(fù)制代碼代碼如下:

<html xmlns="http://www.w3.org/1999/xhtml">  
<head>  
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />  
    <title>Full Permutation(Recursive Backtrack) - Mengliao Software</title>  
</head>  
<body>  
<p>Full Permutation(Recursive Backtrack)<br />  
Mengliao Software Studio - Bosun Network Co., Ltd.<br />  
2012.03.29</p>  
<script type="text/javascript">  
/*  
全排列（遞歸回溯）算法  
1、建立位置數(shù)組，即對位置進(jìn)行排列，排列成功后轉(zhuǎn)換為元素的排列；  
2、建立遞歸函數(shù)，用來搜索第n個(gè)位置；  
3、第n個(gè)位置搜索方式與八皇后問題類似。  
*/ 
var count = 0;  
function show(arr) {  
    document.write("P<sub>" + ++count + "</sub>: " + arr + "<br />");  
}  
function seek(index, n) {  
    if (n >= 0) //判斷是否已回溯到了第一個(gè)位置之前，即已經(jīng)找到了所有位置排列  
        if (index[n] < index.length - 1) { //還有下一個(gè)位置可選  
            index[n]++; //選擇下一個(gè)位置  
            if ((function () { //該匿名函數(shù)判斷該位置是否已經(jīng)被選擇過  
                for (var i = 0; i < n; i++)  
                    if (index[i] == index[n]) return true; //已選擇  
                return false; //未選擇  
            })())  
                return seek(index, n); //重新找位置  
            else 
                return true; //找到  
        }  
        else { //當(dāng)前無位置可選，進(jìn)行遞歸回溯  
            index[n] = -1; //取消當(dāng)前位置  
            if (seek(index, n - 1)) //繼續(xù)找上一個(gè)位置  
                return seek(index, n); //重新找當(dāng)前位置  
            else 
                return false; //已無位置可選  
        }  
    else 
        return false;  
}  
function perm(arr) {  
    var index = new Array(arr.length);  
    for (var i = 0; i < index.length; i++)  
        index[i] = -1; //初始化所有位置為-1，以便++后為0  
    for (i = 0; i < index.length - 1; i++)  
        seek(index, i); //先搜索前n-1個(gè)位置  
    while (seek(index, index.length - 1)) { //不斷搜索第n個(gè)位置，即找到所有位置排列  
        var temp = [];  
        for (i = 0; i < index.length; i++) //將位置之轉(zhuǎn)換為元素  
            temp.push(arr[index[i]]);  
        show(temp);  
    }  
}  
perm(["e1", "e2", "e3", "e4"]);  
</script>  
</body>  
</html> 

算法四：回溯（非遞歸）

復(fù)制代碼代碼如下:

<html xmlns="http://www.w3.org/1999/xhtml">  
<head>  
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />  
    <title>Full Permutation(Non-recursive Backtrack) - Mengliao Software</title>  
</head>  
<body>  
<p>  
Full Permutation(Non-recursive Backtrack)<br />  
Mengliao Software Studio - Bosun Network Co., Ltd.<br />  
2012.03.29</p>  
<script type="text/javascript">  
/*  
全排列（非遞歸回溯）算法  
1、建立位置數(shù)組，即對位置進(jìn)行排列，排列成功后轉(zhuǎn)換為元素的排列；  
2、第n個(gè)位置搜索方式與八皇后問題類似。  
*/ 
var count = 0;  
function show(arr) {  
    document.write("P<sub>" + ++count + "</sub>: " + arr + "<br />");  
}  
function seek(index, n) {  
    var flag = false, m = n; //flag為找到位置排列的標(biāo)志，m保存正在搜索哪個(gè)位置  
    do {  
        index[n]++;  
        if (index[n] == index.length) //已無位置可用  
            index[n--] = -1; //重置當(dāng)前位置，回退到上一個(gè)位置  
        else if (!(function () {  
            for (var i = 0; i < n; i++)  
                if (index[i] == index[n]) return true;  
            return false;  
        })()) //該位置未被選擇  
            if (m == n) //當(dāng)前位置搜索完成  
                flag = true;  
            else 
                n++;  
    } while (!flag && n >= 0)  
    return flag;  
}  
function perm(arr) {  
    var index = new Array(arr.length);  
    for (var i = 0; i < index.length; i++)  
        index[i] = -1;  
    for (i = 0; i < index.length - 1; i++)  
        seek(index, i);  
    while (seek(index, index.length - 1)) {  
        var temp = [];  
        for (i = 0; i < index.length; i++)  
            temp.push(arr[index[i]]);  
        show(temp);  
    }  
}  
perm(["e1", "e2", "e3", "e4"]);  
</script>  
</body>  
</html> 

算法五：排序（非遞歸）

復(fù)制代碼代碼如下:

<html xmlns="http://www.w3.org/1999/xhtml">  
<head>  
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />  
    <title>Full Permutation(Non-recursive Sort) - Mengliao Software</title>  
</head>  
<body>  
<p>  
Full Permutation(Non-recursive Sort)<br />  
Mengliao Software Studio - Bosun Network Co., Ltd.<br />  
2012.03.30</p>  
<script type="text/javascript">  
/*  
全排列（非遞歸求順序）算法  
1、建立位置數(shù)組，即對位置進(jìn)行排列，排列成功后轉(zhuǎn)換為元素的排列；  
2、按如下算法求全排列：  
設(shè)P是1～n(位置編號(hào))的一個(gè)全排列：p = p1,p2...pn = p1,p2...pj-1,pj,pj+1...pk-1,pk,pk+1...pn  
(1)從排列的尾部開始，找出第一個(gè)比右邊位置編號(hào)小的索引j（j從首部開始計(jì)算），即j = max{i | pi < pi+1}  
(2)在pj的右邊的位置編號(hào)中，找出所有比pj大的位置編號(hào)中最小的位置編號(hào)的索引k，即 k = max{i | pi > pj}  
   pj右邊的位置編號(hào)是從右至左遞增的，因此k是所有大于pj的位置編號(hào)中索引最大的  
(3)交換pj與pk  
(4)再將pj+1...pk-1,pk,pk+1...pn翻轉(zhuǎn)得到排列p' = p1,p2...pj-1,pj,pn...pk+1,pk,pk-1...pj+1  
(5)p'便是排列p的下一個(gè)排列  

例如：  
24310是位置編號(hào)0～4的一個(gè)排列，求它下一個(gè)排列的步驟如下：  
(1)從右至左找出排列中第一個(gè)比右邊數(shù)字小的數(shù)字2；  
(2)在該數(shù)字后的數(shù)字中找出比2大的數(shù)中最小的一個(gè)3；  
(3)將2與3交換得到34210；  
(4)將原來2（當(dāng)前3）后面的所有數(shù)字翻轉(zhuǎn)，即翻轉(zhuǎn)4210，得30124；  
(5)求得24310的下一個(gè)排列為30124。  
*/ 
var count = 0;  
function show(arr) {  
    document.write("P<sub>" + ++count + "</sub>: " + arr + "<br />");  
}  
function swap(arr, i, j) {  
    var t = arr[i];  
    arr[i] = arr[j];  
    arr[j] = t;  

}  
function sort(index) {  
    for (var j = index.length - 2; j >= 0 && index[j] > index[j + 1]; j--)  
        ; //本循環(huán)從位置數(shù)組的末尾開始，找到第一個(gè)左邊小于右邊的位置，即j  
    if (j < 0) return false; //已完成全部排列  
    for (var k = index.length - 1; index[k] < index[j]; k--)  
        ; //本循環(huán)從位置數(shù)組的末尾開始，找到比j位置大的位置中最小的，即k  
    swap(index, j, k);  
    for (j = j + 1, k = index.length - 1; j < k; j++, k--)  
        swap(index, j, k); //本循環(huán)翻轉(zhuǎn)j+1到末尾的所有位置  
    return true;  
}  
function perm(arr) {  
    var index = new Array(arr.length);  
    for (var i = 0; i < index.length; i++)  
        index[i] = i;  
    do {  
        var temp = [];  
        for (i = 0; i < index.length; i++)  
            temp.push(arr[index[i]]);  
        show(temp);  
    } while (sort(index));  
}  
perm(["e1", "e2", "e3", "e4"]);  
</script>  
</body>  
</html> 

算法六：求模（非遞歸）

復(fù)制代碼代碼如下:

<html xmlns="http://www.w3.org/1999/xhtml">  
<head>  
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />  
    <title>Full Permutation(Non-recursive Modulo) - Mengliao Software</title>  
</head>  
<body>  
<p>Full Permutation(Non-recursive Modulo)<br />  
Mengliao Software Studio - Bosun Network Co., Ltd.<br />  
2012.03.29</p>  
<script type="text/javascript">  
/*  
全排列（非遞歸求模）算法  
1、初始化存放全排列結(jié)果的數(shù)組result，與原數(shù)組的元素個(gè)數(shù)相等；  
2、計(jì)算n個(gè)元素全排列的總數(shù)，即n!；  
3、從>=0的任意整數(shù)開始循環(huán)n!次，每次累加1，記為index；  
4、取第1個(gè)元素arr[0]，求1進(jìn)制的表達(dá)最低位，即求index模1的值w，將第1個(gè)元素（arr[0]）插入result的w位置，并將index迭代為index\1；  
5、取第2個(gè)元素arr[1]，求2進(jìn)制的表達(dá)最低位，即求index模2的值w，將第2個(gè)元素（arr[1]）插入result的w位置，并將index迭代為index\2；  
6、取第3個(gè)元素arr[2]，求3進(jìn)制的表達(dá)最低位，即求index模3的值w，將第3個(gè)元素（arr[2]）插入result的w位置，并將index迭代為index\3；  
7、……  
8、直到取最后一個(gè)元素arr[arr.length-1]，此時(shí)求得一個(gè)排列；  
9、當(dāng)index循環(huán)完成，便求得所有排列。  

例：  
求4個(gè)元素["a", "b", "c", "d"]的全排列, 共循環(huán)4!=24次，可從任意>=0的整數(shù)index開始循環(huán)，每次累加1，直到循環(huán)完index+23后結(jié)束；  
假設(shè)index=13（或13+24，13+2*24，13+3*24…），因?yàn)楣?個(gè)元素，故迭代4次，則得到的這一個(gè)排列的過程為：  
第1次迭代，13/1，商=13，余數(shù)=0，故第1個(gè)元素插入第0個(gè)位置（即下標(biāo)為0），得["a"]；  
第2次迭代，13/2, 商=6，余數(shù)=1，故第2個(gè)元素插入第1個(gè)位置（即下標(biāo)為1），得["a", "b"]；  
第3次迭代，6/3, 商=2，余數(shù)=0，故第3個(gè)元素插入第0個(gè)位置（即下標(biāo)為0），得["c", "a", "b"]；  
第4次迭代，2/4，商=0，余數(shù)=2, 故第4個(gè)元素插入第2個(gè)位置（即下標(biāo)為2），得["c", "a", "d", "b"]；  
*/ 
var count = 0;  
function show(arr) {  
    document.write("P<sub>" + ++count + "</sub>: " + arr + "<br />");  
}  
function perm(arr) {  
    var result = new Array(arr.length);  
    var fac = 1;  
    for (var i = 2; i <= arr.length; i++)  
        fac *= i;  
    for (index = 0; index < fac; index++) {  
        var t = index;  
        for (i = 1; i <= arr.length; i++) {  
            var w = t % i;  
            for (j = i - 1; j > w; j--)  
                result[j] = result[j - 1];  
            result[w] = arr[i - 1];  
            t = Math.floor(t / i);  
        }  
        show(result);  
    }  
}  
perm(["e1", "e2", "e3", "e4"]);  
</script>  
</body>  
</html> 