javascript如何返回字符串的所有排列

目录js返回字符串的所有排列需求代码一点思路js实现字符串全排序总结js返回字符串的所有排列需求返回一个字符串所有的排列输入:一个字符串输出:一个包含该字符串所有排列情况的数组代码constanag...

目录
js返回字符串的所有排列
需求
代码
一点思路
js实现字符串全排序
总结

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,php那么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以上的开始计算
        /* 先把字符串转成数组,因为js里关于字符串的函数不多,而关于数组的函数很多,所以中间步骤我们都用数组处理,比较方便 */
 
var arrayStr = str.split('');
        /* 定义一个中间数组,作为每次大循环的根基。比如,你开始拿第3个字符去填充空位,那前2个字符的全排列就已经都存储在中间数组里了 */
        // 你开始拿第4个字符去填充空位,那前3个字符的全排列就已经都存储在中间数组里了
 
var transArray = [];
        /* 先把字符串的第1个字符存入中间数组,这是我们盖高楼的地基。此字符产生的两个空位,我们拿第2个字符开始去填充 */
transArray.push(arrayStr[0]);
        // 定义一个存储最终结果的数组,作为返回值
var resultArray = [];
        /* 第一层循环,从第2个字符开始,每次向字符串后取一个字符,往 中间数组 的每个字符串的 空位 里插 */
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

总结

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

延伸阅读:

上一篇:Vue body样式修改方式

下一篇:Nodejs如何解决跨域(CORS)