JavaScript算法系列之

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

字符串拼接

（先理解不输入重复字符的）

1 1 function permutate(str) {
2 2     var result=[];
3 3     if(str.length==1){
4 4         return [str]    
5 5     }else{  
6 6         var preResult=permutate(str.slice(1));
7 7         for (var j = 0; j < preResult.length; j++) {
8 8             for (var k = 0; k < preResult[j].length+1; k++) {
9 9                 var temp=preResult[j].slice(0,k)+str[0]+preResult[j].slice(k);   
1010                 result.push(temp);              
1111             }
1212         }
1313         return result;
1414     }  
1515 }
1616 console.log(permutate("abc"));

上述方式不是用交换实现的 用的是字符串拼接的方法

原理：

固定第一个字符，递归取得第一个字符后面的各种字符串组合；

再把第一个字符与后面每一个字符交换，并同样递归获得收尾后面的字符串组合；

递归的出口为当只有一个字符的时候

理解的不用看一下算法流程了！

=============================================================================================================

假设输入abc

大概走一遍算法执行流程：

第一步 str='abc';

第二步 到6行 preResult='bc' 递归

第三步 到6行  preResult='c' 递归

第四步 到第四行返回 [c]  此时回到第三步的递归 str = 'bc' 执行第7行往下的循环

循环完毕后result=['bc','cb'] 此时返回第二步的递归 str='abc' 执行7行往下的循环

第五步 循环完毕后result=['abc','bac','bca','acb','cab','cba'] 此时输出最终结果

 ============================================================================================================

字符串交换

1 1 function permutation(str){
2 2     let result = [];
3 3     if(str.length === 1){
4 4         return [str];
5 5     }else{
6 6         let last = permutation(str.slice(1));
7 7         for(let i=0; i<last.length;i++){
8 8             let ss = swap(str[0],last[i],result);
9 9             result=ss;
1010         }
1111         return result;
1212     }
1313 }
1414 function swap(a,b,result){
1515     for(let i=0;i<b.length+1;i++){
1616         let newStr = b;
1717         let sss = newStr.split('');
1818         sss.splice(i,0,a); 
1919         result.push(sss.join(''))      
2020     }
2121     return result;
2222 }
2323 
2424 let res = permutation('abc');
2525 console.log(res);

对于有重复的字符串来说按照上述算法输出出来会有重复的组合，偷懒的解法是直接去重就可以了

加一句Array.from(new Set(permutate("abc")));