全排列是一种时间复杂度为O(n!)的算法前两天给学生讲课无意间想到这个问题回来总结了一下可以由种算法求解其中动态循环类似回溯算法实现起来比较繁琐故总结了种以飨读者所有算法均使用JavaScript编写可直接运行
算法一交换（递归）
复制代码 代码如下:
<html xmlns="
<head>
<meta http
equiv="Content
Type" 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(arr
i
j) {
if(i!=j) {
var temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
var count=
;
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+
<arr
length
) //判断数组中剩余的待全排列的元素是否大于
个
fn(n+
); //从第n+
个下标进行全排列
else
show(arr); //显示一组结果
swap(arr
i
n);
}
})(
);
}
perm(["e
"
"e
"
"e
"
"e
"]);
</script>
</body>
</html>
算法二链接（递归）
复制代码 代码如下:
<html xmlns="
<head>
<meta http
equiv="Content
Type" 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) {
document
write("P<sub>"+ ++count+"</sub>: "+arr+"<br />");
}
function perm(arr) {
(function fn(source
result) {
if (source
length ==
)
show(result);
else
for (var i =
; i < source
length; i++)
fn(source
slice(
i)
concat(source
slice(i +
))
result
concat(source[i]));
})(arr
[]);
}
perm(["e
"
"e
"
"e
"
"e
"]);
</script>
</body>
</html>
算法三回溯（递归）
复制代码 代码如下:
<html xmlns="
<head>
<meta http
equiv="Content
Type" 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) {
document
write("P<sub>" + ++count + "</sub>: " + arr + "<br />");
}
function seek(index
n) {
if (n >=
) //判断是否已回溯到了第一个位置之前
即已经找到了所有位置排列
if (index[n] < index
length
) { //还有下一个位置可选
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(arr
length);
for (var i =
; i < index
length; i++)
index[i] =
; //初始化所有位置为
以便++后为
for (i =
; i < index
length
; i++)
seek(index
i); //先搜索前n
个位置
while (seek(index
index
length
)) { //不断搜索第n个位置
即找到所有位置排列
var temp = [];
for (i =
; i < index
length; i++) //将位置之转换为元素
temp
push(arr[index[i]]);
show(temp);
}
}
perm(["e
"
"e
"
"e
"
"e
"]);
</script>
</body>
</html>
算法四回溯（非递归）
复制代码 代码如下:
<html xmlns="
<head>
<meta http
equiv="Content
Type" content="text/html; charset=utf
" />
<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 />
</p>
<script type="text/javascript">
/*
全排列（非递归回溯）算法
建立位置数组
即对位置进行排列
排列成功后转换为元素的排列
第n个位置搜索方式与八皇后问题类似
*/
var count =
;
function show(arr) {
document
write("P<sub>" + ++count + "</sub>: " + arr + "<br />");
}
function seek(index
n) {
var flag = false
m = n; //flag为找到位置排列的标志
m保存正在搜索哪个位置
do {
index[n]++;
if (index[n] == index
length) //已无位置可用
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(arr
length);
for (var i =
; i < index
length; i++)
index[i] =
;
for (i =
; i < index
length
; i++)
seek(index
i);
while (seek(index
index
length
)) {
var temp = [];
for (i =
; i < index
length; i++)
temp
push(arr[index[i]]);
show(temp);
}
}
perm(["e
"
"e
"
"e
"
"e
"]);
</script>
</body>
</html>
算法五排序（非递归）
复制代码 代码如下:
<html xmlns="
<head>
<meta http
equiv="Content
Type" content="text/html; charset=utf
" />
<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 />
</p>
<script type="text/javascript">
/*
全排列（非递归求顺序）算法
建立位置数组
即对位置进行排列
排列成功后转换为元素的排列
按如下算法求全排列
设P是
～n(位置编号)的一个全排列
p = p
p
pn = p
p
pj
pj
pj+
pk
pk
pk+
pn
(
)从排列的尾部开始
找出第一个比右边位置编号小的索引j（j从首部开始计算）
即j = max{i | pi < pi+
}
(
)在pj的右边的位置编号中
找出所有比pj大的位置编号中最小的位置编号的索引k
即 k = max{i | pi > pj}
pj右边的位置编号是从右至左递增的
因此k是所有大于pj的位置编号中索引最大的
(
)交换pj与pk
(
)再将pj+
pk
pk
pk+
pn翻转得到排列p
= p
p
pj
pj
pn
pk+
pk
pk
pj+
(
)p
便是排列p的下一个排列
例如
是位置编号
～
的一个排列
求它下一个排列的步骤如下
(
)从右至左找出排列中第一个比右边数字小的数字
(
)在该数字后的数字中找出比
大的数中最小的一个
(
)将
与
交换得到
(
)将原来
（当前
）后面的所有数字翻转
即翻转
得
(
)求得
的下一个排列为
*/
var count =
;
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
; j >=
&& index[j] > index[j +
]; j
)
; //本循环从位置数组的末尾开始
找到第一个左边小于右边的位置
即j
if (j <
) return false; //已完成全部排列
for (var k = index
length
; index[k] < index[j]; k
)
; //本循环从位置数组的末尾开始
找到比j位置大的位置中最小的
即k
swap(index
j
k);
for (j = j +
k = index
length
; j < k; j++
k
)
swap(index
j
k); //本循环翻转j+
到末尾的所有位置
return true;
}
function perm(arr) {
var index = new Array(arr
length);
for (var i =
; i < index
length; i++)
index[i] = i;
do {
var temp = [];
for (i =
; i < index
length; i++)
temp
push(arr[index[i]]);
show(temp);
} while (sort(index));
}
perm(["e
"
"e
"
"e
"
"e
"]);
</script>
</body>
</html>
算法六求模（非递归）
复制代码 代码如下:
<html xmlns="
<head>
<meta http
equiv="Content
Type" content="text/html; charset=utf
" />
<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 />
</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[arr
length
]
此时求得一个排列
当index循环完成
便求得所有排列
例
求
个元素["a"
"b"
"c"
"d"]的全排列
共循环
!=
次
可从任意>=
的整数index开始循环
每次累加
直到循环完index+
后结束
假设index=
（或
+
+
*
+
*
…）
因为共
个元素
故迭代
次
则得到的这一个排列的过程为
第
次迭代
/
商=
余数=
故第
个元素插入第
个位置（即下标为
）
得["a"]
第
次迭代
/
商=
余数=
故第
个元素插入第
个位置（即下标为
）
得["a"
"b"]
第
次迭代
/
商=
余数=
故第
个元素插入第
个位置（即下标为
）
得["c"
"a"
"b"]
第
次迭代
/
商=
余数=
故第
个元素插入第
个位置（即下标为
）
得["c"
"a"
"d"
"b"]
*/
var count =
;
function show(arr) {
document
write("P<sub>" + ++count + "</sub>: " + arr + "<br />");
}
function perm(arr) {
var result = new Array(arr
length);
var fac =
;
for (var i =
; i <= arr
length; i++)
fac *= i;
for (index =
; index < fac; index++) {
var t = index;
for (i =
; i <= arr
length; i++) {
var w = t % i;
for (j = i
; j > w; j
)
result[j] = result[j
];
result[w] = arr[i
];
t = Math
floor(t / i);
}
show(result);
}
}
perm(["e
"
"e
"
"e
"
"e
"]);
</script>
</body>
</html>
上面的六种算法有些是对位置进行排列例如回溯排序等因为这样可以适应各种类型的元素而非要求待排列元素一定是数字或字母等
