js中字符串的全排列的算法解析

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

分析

没啥好分析的了，这个题不会，上网查的思路，大概就是：

abc分化为abc、bac、cba（这是0和0交换、0和1交换、0和2交换

第一步得出的abc分化为abc、acb（这是1和1交换、1和2交换

第一步得出的bac分化为bac、bca（这是1和1交换、1和2交换

第一步得出的cba分化为cba、cab（这是1和1交换、1和2交换

代码实现

function Permutation(str)
{
 if(str === null || str === "")
 return [];
 var res = [];
 var index = 0;
 
 step(str.split(""), index, res);
 
 return res.sort();
}

function step(strArr, cur, res) {
 if(cur === strArr.length-1){
 var i = 0, str = "";
 while(i < strArr.length){
 str += strArr[i++];
 }
 res.push(str);
 }
 
 for(var i = cur;i < strArr.length;i++) {
 if(strArr[i] === strArr[cur] && i !== cur)
 continue;
 swap(strArr, i, cur);
 step(strArr, cur+1, res);
 swap(strArr, i, cur);
 }
}

function swap(arr, a, b) {
 var temp = arr[a];
 arr[a] = arr[b];
 arr[b] = temp;
}