JavaScript全排列的六种算法 具体实现
2024-05-06 14:38:23
供稿：网友
全排列是一种时间复杂度为：O(n!)的算法，前两天给学生讲课，无意间想到这个问题，回来总结了一下，可以由7种算法求解，其中动态循环类似回溯算法，实现起来比较繁琐，故总结了6种，以飨读者。所有算法均使用JavaScript编写，可直接运行。
算法一：交换（递归）
代码如下:
<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、将第一个位置分别放置各个不同的元素；
2、对剩余的位置进行全排列（递归）；
3、递归出口为只对一个元素进行全排列。
*/
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个位置选择元素
for(var i=n;i<arr.length;i++) {
swap(arr,i,n);
if(n+1<arr.length-1) //判断数组中剩余的待全排列的元素是否大于1个
fn(n+1); //从第n+1个下标进行全排列
else
show(arr); //显示一组结果
swap(arr,i,n);
}
})(0);
}
perm(["e1","e2","e3","e4"]);
</script>
</body>
</html>
算法二：链接（递归）
代码如下:
<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>
