JavaScript全排列的六种算法

全排列是一种时间复杂度为：O(n!)的算法，前两天给学生讲课，无意间想到这个问题，回来总结了一下，可以由7种算法求解，其中动态循环类似回溯算法，实现起来比较繁琐，故总结了6种，以飨读者。所有算法均使用JavaScript编写，可直接运行。
算法一：交换（递归）
1. <html xmlns="http://www.w3.org/1999/xhtml">
2. <head>
3.     <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
4.     <title>Full Permutation(Recursive Swap) - Mengliao Software</title>
5. </head>
6. <body>
7. <p>Full Permutation(Recursive Swap)<br />
8. Mengliao Software Studio - Bosun Network Co., Ltd.<br />
9. 2011.05.24</p>
10. <script type="text/javascript">
11. /*
12. 全排列（递归交换）算法
13. 1、将第一个位置分别放置各个不同的元素；
14. 2、对剩余的位置进行全排列（递归）；
15. 3、递归出口为只对一个元素进行全排列。
16. */
17. function swap(arr,i,j) {
18.     if(i!=j) {
19.         var temp=arr[i];
20.         arr[i]=arr[j];
21.         arr[j]=temp;
22.     }
23. }
24. var count=0;
25. function show(arr) {
26.     document.write("P<sub>"+ ++count+"</sub>: "+arr+"<br />");
27. }
28. function perm(arr) {
29.     (function fn(n) { //为第n个位置选择元素
30.         for(var i=n;i<arr.length;i++) {
31.             swap(arr,i,n);
32.             if(n+1<arr.length-1) //判断数组中剩余的待全排列的元素是否大于1个
33.                 fn(n+1); //从第n+1个下标进行全排列
34.             else
35.                 show(arr); //显示一组结果
36.             swap(arr,i,n);
37.         }
38.     })(0);
39. }
40. perm(["e1","e2","e3","e4"]);
41. </script>
42. </body>
43. </html>
算法二：链接（递归）
1. <html xmlns="http://www.w3.org/1999/xhtml">
2. <head>
3.     <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
4.     <title>Full Permutation(Recursive Link) - Mengliao Software</title>
5. </head>
6. <body>
7. <p>Full Permutation(Recursive Link)<br />
8. Mengliao Software Studio - Bosun Network Co., Ltd.<br />
9. 2012.03.29</p>
10. <script type="text/javascript">
11. /*
12. 全排列（递归链接）算法
13. 1、设定源数组为输入数组，结果数组存放排列结果（初始化为空数组）；
14. 2、逐一将源数组的每个元素链接到结果数组中（生成新数组对象）；
15. 3、从原数组中删除被链接的元素（生成新数组对象）；
16. 4、将新的源数组和结果数组作为参数递归调用步骤2、3，直到源数组为空，则输出一个排列。
17. */
18. var count=0;
19. function show(arr) {
20.     document.write("P<sub>"+ ++count+"</sub>: "+arr+"<br />");
21. }
22. function perm(arr) {
23.     (function fn(source, result) {
24.         if (source.length == 0)
25.             show(result);
26.         else
27.             for (var i = 0; i < source.length; i++)
28.                 fn(source.slice(0, i).concat(source.slice(i + 1)), result.concat(source[i]));
29.     })(arr, []);
30. }
31. perm(["e1", "e2", "e3", "e4"]);
32. </script>
33. </body>
34. </html>
算法三：回溯（递归）
1. <html xmlns="http://www.w3.org/1999/xhtml">
2. <head>
3.     <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
4.     <title>Full Permutation(Recursive Backtrack) - Mengliao Software</title>
5. </head>
6. <body>
7. <p>Full Permutation(Recursive Backtrack)<br />
8. Mengliao Software Studio - Bosun Network Co., Ltd.<br />
9. 2012.03.29</p>
10. <script type="text/javascript">
11. /*
12. 全排列（递归回溯）算法
13. 1、建立位置数组，即对位置进行排列，排列成功后转换为元素的排列；
14. 2、建立递归函数，用来搜索第n个位置；
15. 3、第n个位置搜索方式与八皇后问题类似。
16. */
17. var count = 0;
18. function show(arr) {
19.     document.write("P<sub>" + ++count + "</sub>: " + arr + "<br />");
20. }
21. function seek(index, n) {
22.     if (n >= 0) //判断是否已回溯到了第一个位置之前，即已经找到了所有位置排列
23.         if (index[n] < index.length - 1) { //还有下一个位置可选
24.             index[n]++; //选择下一个位置
25.             if ((function () { //该匿名函数判断该位置是否已经被选择过
26.                 for (var i = 0; i < n; i++)
27.                     if (index[i] == index[n]) return true; //已选择
28.                 return false; //未选择
29.             })())
30.

补充：web前端 , JavaScript ,