熱點推薦：
您现在的位置： 電腦知識網 >> 編程 >> Java編程 >> JSP教程 >> 正文

JavaScript全排列的六種算法 具體實現

2022-06-13   來源: JSP教程 

　　全排列是一種時間復雜度為O(n!)的算法前兩天給學生講課無意間想到這個問題回來總結了一下可以由種算法求解其中動態循環類似回溯算法實現起來比較繁瑣故總結了種以飨讀者所有算法均使用JavaScript編寫可直接運行
算法一交換（遞歸）

復制代碼 代碼如下:
<html xmlns="
<head>
<meta httpequiv="ContentType" content="text/html; charset=utf" />
<title>Full Permutation(Recursive Swap) Mengliao Software</title>
</head>
<body>
<p>Full Permutation(Recursive Swap)<br />
Mengliao Software Studio Bosun Network Co Ltd<br />
</p>
<script type="text/javascript">
/*
全排列（遞歸交換）算法
將第一個位置分別放置各個不同的元素
對剩余的位置進行全排列（遞歸）
遞歸出口為只對一個元素進行全排列
*/
function swap(arrij) {
if(i!=j) {
var temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
var count=;
function show(arr) {
documentwrite("P<sub>"+ ++count+"</sub>: "+arr+"<br />");
}
function perm(arr) {
(function fn(n) { //為第n個位置選擇元素
for(var i=n;i<arrlength;i++) {
swap(arrin);
if(n+<arrlength) //判斷數組中剩余的待全排列的元素是否大於個
fn(n+); //從第n+個下標進行全排列
else
show(arr); //顯示一組結果
swap(arrin);
}
})();
}
perm(["e""e""e""e"]);
</script>
</body>
</html>

　　
算法二鏈接（遞歸）

復制代碼 代碼如下:
<html xmlns="
<head>
<meta httpequiv="ContentType" content="text/html; charset=utf" />
<title>Full Permutation(Recursive Link) Mengliao Software</title>
</head>
<body>
<p>Full Permutation(Recursive Link)<br />
Mengliao Software Studio Bosun Network Co Ltd<br />
</p>
<script type="text/javascript">
/*
全排列（遞歸鏈接）算法
設定源數組為輸入數組結果數組存放排列結果（初始化為空數組）
逐一將源數組的每個元素鏈接到結果數組中（生成新數組對象）
從原數組中刪除被鏈接的元素（生成新數組對象）
將新的源數組和結果數組作為參數遞歸調用步驟直到源數組為空則輸出一個排列
*/
var count=;
function show(arr) {
documentwrite("P<sub>"+ ++count+"</sub>: "+arr+"<br />");
}
function perm(arr) {
(function fn(source result) {
if (sourcelength == )
show(result);
else
for (var i = ; i < sourcelength; i++)
fn(sourceslice( i)concat(sourceslice(i + )) resultconcat(source[i]));
})(arr []);
}
perm(["e" "e" "e" "e"]);
</script>
</body>
</html>

　　
算法三回溯（遞歸）

復制代碼 代碼如下:
<html xmlns="
<head>
<meta httpequiv="ContentType" content="text/html; charset=utf" />
<title>Full Permutation(Recursive Backtrack) Mengliao Software</title>
</head>
<body>
<p>Full Permutation(Recursive Backtrack)<br />
Mengliao Software Studio Bosun Network Co Ltd<br />
</p>
<script type="text/javascript">
/*
全排列（遞歸回溯）算法
建立位置數組即對位置進行排列排列成功後轉換為元素的排列
建立遞歸函數用來搜索第n個位置
第n個位置搜索方式與八皇後問題類似
*/
var count = ;
function show(arr) {
documentwrite("P<sub>" + ++count + "</sub>: " + arr + "<br />");
}
function seek(index n) {
if (n >= ) //判斷是否已回溯到了第一個位置之前即已經找到了所有位置排列
if (index[n] < indexlength ) { //還有下一個位置可選
index[n]++; //選擇下一個位置
if ((function () { //該匿名函數判斷該位置是否已經被選擇過
for (var i = ; i < n; i++)
if (index[i] == index[n]) return true; //已選擇
return false; //未選擇
})())
return seek(index n); //重新找位置
else
return true; //找到
}
else { //當前無位置可選進行遞歸回溯
index[n] = ; //取消當前位置
if (seek(index n )) //繼續找上一個位置
return seek(index n); //重新找當前位置
else
return false; //已無位置可選
}
else
return false;
}
function perm(arr) {
var index = new Array(arrlength);
for (var i = ; i < indexlength; i++)
index[i] = ; //初始化所有位置為以便++後為
for (i = ; i < indexlength ; i++)
seek(index i); //先搜索前n個位置
while (seek(index indexlength )) { //不斷搜索第n個位置即找到所有位置排列
var temp = [];
for (i = ; i < indexlength; i++) //將位置之轉換為元素
temppush(arr[index[i]]);
show(temp);
}
}
perm(["e" "e" "e" "e"]);
</script>
</body>
</html>

　　
算法四回溯（非遞歸）

復制代碼 代碼如下:
<html xmlns="
<head>
<meta httpequiv="ContentType" content="text/html; charset=utf" />
<title>Full Permutation(Nonrecursive Backtrack) Mengliao Software</title>
</head>
<body>
<p>
Full Permutation(Nonrecursive Backtrack)<br />
Mengliao Software Studio Bosun Network Co Ltd<br />
</p>
<script type="text/javascript">
/*
全排列（非遞歸回溯）算法
建立位置數組即對位置進行排列排列成功後轉換為元素的排列
第n個位置搜索方式與八皇後問題類似
*/
var count = ;
function show(arr) {
documentwrite("P<sub>" + ++count + "</sub>: " + arr + "<br />");
}
function seek(index n) {
var flag = false m = n; //flag為找到位置排列的標志m保存正在搜索哪個位置
do {
index[n]++;
if (index[n] == indexlength) //已無位置可用
index[n] = ; //重置當前位置回退到上一個位置
else if (!(function () {
for (var i = ; i < n; i++)
if (index[i] == index[n]) return true;
return false;
})()) //該位置未被選擇
if (m == n) //當前位置搜索完成
flag = true;
else
n++;
} while (!flag && n >= )
return flag;
}
function perm(arr) {
var index = new Array(arrlength);
for (var i = ; i < indexlength; i++)
index[i] = ;
for (i = ; i < indexlength ; i++)
seek(index i);
while (seek(index indexlength )) {
var temp = [];
for (i = ; i < indexlength; i++)
temppush(arr[index[i]]);
show(temp);
}
}
perm(["e" "e" "e" "e"]);
</script>
</body>
</html>

　　
算法五排序（非遞歸）

復制代碼 代碼如下:
<html xmlns="
<head>
<meta httpequiv="ContentType" content="text/html; charset=utf" />
<title>Full Permutation(Nonrecursive Sort) Mengliao Software</title>
</head>
<body>
<p>
Full Permutation(Nonrecursive Sort)<br />
Mengliao Software Studio Bosun Network Co Ltd<br />
</p>
<script type="text/javascript">
/*
全排列（非遞歸求順序）算法
建立位置數組即對位置進行排列排列成功後轉換為元素的排列
按如下算法求全排列
設P是～n(位置編號)的一個全排列p = pppn = pppjpjpj+pkpkpk+pn
()從排列的尾部開始找出第一個比右邊位置編號小的索引j（j從首部開始計算）即j = max{i | pi < pi+}
()在pj的右邊的位置編號中找出所有比pj大的位置編號中最小的位置編號的索引k即 k = max{i | pi > pj}
pj右邊的位置編號是從右至左遞增的因此k是所有大於pj的位置編號中索引最大的
()交換pj與pk
()再將pj+pkpkpk+pn翻轉得到排列p = pppjpjpnpk+pkpkpj+
()p便是排列p的下一個排列

例如
是位置編號～的一個排列求它下一個排列的步驟如下
()從右至左找出排列中第一個比右邊數字小的數字
()在該數字後的數字中找出比大的數中最小的一個
()將與交換得到
()將原來（當前）後面的所有數字翻轉即翻轉得
()求得的下一個排列為
*/
var count = ;
function show(arr) {
documentwrite("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 = indexlength ; j >= && index[j] > index[j + ]; j)
; //本循環從位置數組的末尾開始找到第一個左邊小於右邊的位置即j
if (j < ) return false; //已完成全部排列
for (var k = indexlength ; index[k] < index[j]; k)
; //本循環從位置數組的末尾開始找到比j位置大的位置中最小的即k
swap(index j k);
for (j = j + k = indexlength ; j < k; j++ k)
swap(index j k); //本循環翻轉j+到末尾的所有位置
return true;
}
function perm(arr) {
var index = new Array(arrlength);
for (var i = ; i < indexlength; i++)
index[i] = i;
do {
var temp = [];
for (i = ; i < indexlength; i++)
temppush(arr[index[i]]);
show(temp);
} while (sort(index));
}
perm(["e" "e" "e" "e"]);
</script>
</body>
</html>

　　
算法六求模（非遞歸）

復制代碼 代碼如下:
<html xmlns="
<head>
<meta httpequiv="ContentType" content="text/html; charset=utf" />
<title>Full Permutation(Nonrecursive Modulo) Mengliao Software</title>
</head>
<body>
<p>Full Permutation(Nonrecursive Modulo)<br />
Mengliao Software Studio Bosun Network Co Ltd<br />
</p>
<script type="text/javascript">
/*
全排列（非遞歸求模）算法
初始化存放全排列結果的數組result與原數組的元素個數相等
計算n個元素全排列的總數即n!
從>=的任意整數開始循環n!次每次累加記為index
取第個元素arr[]求進制的表達最低位即求index模的值w將第個元素（arr[]）插入result的w位置並將index迭代為index
取第個元素arr[]求進制的表達最低位即求index模的值w將第個元素（arr[]）插入result的w位置並將index迭代為index
取第個元素arr[]求進制的表達最低位即求index模的值w將第個元素（arr[]）插入result的w位置並將index迭代為index
……
直到取最後一個元素arr[arrlength]此時求得一個排列
當index循環完成便求得所有排列

例
求個元素["a" "b" "c" "d"]的全排列 共循環!=次可從任意>=的整數index開始循環每次累加直到循環完index+後結束
假設index=（或++*+*…）因為共個元素故迭代次則得到的這一個排列的過程為
第次迭代/商=余數=故第個元素插入第個位置（即下標為）得["a"]
第次迭代/ 商=余數=故第個元素插入第個位置（即下標為）得["a" "b"]
第次迭代/ 商=余數=故第個元素插入第個位置（即下標為）得["c" "a" "b"]
第次迭代/商=余數= 故第個元素插入第個位置（即下標為）得["c" "a" "d" "b"]
*/
var count = ;
function show(arr) {
documentwrite("P<sub>" + ++count + "</sub>: " + arr + "<br />");
}
function perm(arr) {
var result = new Array(arrlength);
var fac = ;
for (var i = ; i <= arrlength; i++)
fac *= i;
for (index = ; index < fac; index++) {
var t = index;
for (i = ; i <= arrlength; i++) {
var w = t % i;
for (j = i ; j > w; j)
result[j] = result[j ];
result[w] = arr[i ];
t = Mathfloor(t / i);
}
show(result);
}
}
perm(["e" "e" "e" "e"]);
</script>
</body>
</html>

　　
上面的六種算法有些是對位置進行排列例如回溯排序等因為這樣可以適應各種類型的元素而非要求待排列元素一定是數字或字母等


From:http://tw.wingwit.com/Article/program/Java/JSP/201311/19940.html
    《JavaScript全排列的六種算法 具體實現》本文是由JSP教程免費提供，內容來源於互聯網,本文歸原作者所有。
  • 上一篇文章：

  • 下一篇文章：
    • 相關文章
    主板 CPU 硬盤 內存 顯卡 聲卡 顯示器 光驅 死機
    推薦文章
    Copyright © 2005-2022 電腦知識網 Computer Knowledge   All rights reserved.