全排列是一种时间复杂度为:O(n!)的算法,前两天给学生讲课,无意间想到这个问题,回来总结了一下,可以由7种算法求解,其中动态循环类似回溯算法,实现起来比较繁琐,故总结了6种,以飨读者。所有算法均使用JavaScript编写,可直接运行。
Full Permutation(Recursive Swap) - Mengliao Software Full Permutation(Recursive Swap)
Mengliao Software Studio - Bosun Network Co., Ltd.
2011.05.24
输出一个排列。
*/
var count=0;
function show(arr) {
document.write("P
"+ ++count+": "+arr+"
");
}
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>
Full Permutation(Recursive Backtrack) - Mengliao Software Full Permutation(Recursive Backtrack)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29