js返回字符串的所有排列
需求
返回一个字符串所有的排列
- 输入：一个字符串
- 输出：一个包含该字符串所有排列情况的数组
代码
const anagrams = str => {
if (str.length <= 2) {
return str.length === 2 ? [str, str[1] + str[0]] : [str];
}
else{
return str.split('').reduce((acc, letter, i) =>
acc.concat(anagrams(str.slice(0, i) + str.slice(i + 1)).map(val => letter + val)), []);
}
};效果
一点思路
递归、长度为阶乘
js实现字符串全排序
这是一道经典的算法题，学过排列组合的童鞋们都知道长度为n的字符串其全排序大小为n! (这里不考虑字符串里有重复字符，不做去重处理)。
网上有各种语言的实现算法，但js语言实现的比较少（果然藐视【划掉】忽略我广大前端er的算法水平）。另外，网上实现的多为递归方法。这里用非递归的js实现一下，轻拍。
先说一下思路：单个字符的串，比如a全排序为1（废话忽略）。
两个字符的串比如ab，全排序数为2，即：ab和ba。那我们不禁要问，你是怎么得到的？
解答如下：
- 第一步————先拿出a，那么a的前面和a的后面产生两个空位，如图：0 a 0。
- 第二步————将b分别放在两个空位里，得到ba和ab。
- 第三步————sorry，没有第三步。
好了，那三个字符abc你怎么办？
其实还是老办法，只不过我们是建立在刚才的2个字符组成的串已经全排完的基础上。
- 第一步————拿出刚才产生的ba，它产生了三个空位，如图：0 b 0 a 0.
- 第二步————把剩余的c分别插入这三个空位，得到cba，bca和bac。
- 现在我们的ba已经被利用完了，还有ab没用，ok，我们现在来用它重复上面的步骤，得到cab，acb和abc。
那四个字符abcd组成的串呢？
聪明的你一定想到用刚才三个字符产生的结果，每个串生成4个空位，然后把d分别放在这4个空位里。
至此，我们的算法思路就已经说完了。现在开始用代码实现。
function myPermutation(str){
// 空字符串直接返回吧
if(str.length === 0){
console.log('The string you input have No length!');
return;
}
// 一个字符也不用运算
if(str.length === 1){
console.log('The result array is: ' + str, '-&- The array length is: ' + str.length);
return;
}
// 长度2以上的开始计算
var arrayStr = str.split('');
// 你开始拿第4个字符去填充空位，那前3个字符的全排列就已经都存储在中间数组里了
var transArray = [];
transArray.push(arrayStr[0]);
// 定义一个存储最终结果的数组，作为返回值
var resultArray = [];
for(var i = 1; i < arrayStr.length; i++){
resultArray = [];
// 每次新取到的字符
var addChar = arrayStr[i];
for(var j = 0; j < transArray.length; j++){
// 依次取中间数组里的串
var toBeInsertStr = transArray[j];
// 用空格分割字符串，从而产生空位
var toBeInsertStrArray = toBeInsertStr.split('');
// 第三层循环，将取到的新字符分别放到空位上形成字符串，有多少空位就循环几次
for (var k = 0; k <= transArray[j].length; k++){
tempArray = toBeInsertStrArray.concat();
// 用splice函数处理，表示将字符填入空位
var insertedArray = toBeInsertStrArray.splice(k, 0, addChar);
// 刚才是数组操作，现在转成字符串
var transArrayItem = toBeInsertStrArray.join('');
// 将字符串压入结果数组
resultArray.push(transArrayItem);
toBeInsertStrArray = tempArray.concat();
}
}
transArray = [];
transArray = resultArray.concat();
}
console.log('The result array is: ' + resultArray, '-&- The array length is: ' + resultArray.length);
}
myPermutation('');
myPermutation('a');
myPermutation('ab');
myPermutation('abc');运行结果：
The string you input have No length!
The result array is: a -&- The array length is: 1
The result array is: ba,ab -&- The array length is: 2
The result array is: cba,bca,bac,cab,acb,abc -&- The array length is: 6
总结
以上为个人经验，希望能给大家一个参考，也希望大家多多支持编程网。
