时间:2021-07-01 10:21:17 帮助过:3人阅读
输出:["abc","acb","bac","bca","cab","cba"]
- 输入:"abc"
我在实现算法时遇到了一个问题,至今无法解决。但是全排列算法又很重要,所以写这篇文章记录一下。
算法思想:
当字符串长度为1时,输出该字符串;
当长度大于1时,取字符串的首字母,求出长度-1的串的全排列,将首字母插入每一个排列的任意位置。
算法实现:
- function permutate(str) {
- //保存每一轮递归的排列结果
- var result = [];
- //初始条件:长度为1
- if (str.length == 1) {
- return [str]
- } else {
- //求剩余子串的全排列,对每个排列进行遍历
- var preResult = permutate(str.slice(1));
- for (var j = 0; j < preResult.length; j++) {
- for (var k = 0; k < preResult[j].length + 1; k++) {
- //将首字母插入k位置
- var temp = preResult[j].slice(0, k) + str[0] + preResult[j].slice(k);
- result.push(temp);
- }
- }
- return result;
- }
- }
算法应该不难理解吧。但是当传参的字符串是"abcdefghijkl"
时,排列用到的空间是12!=479001600
,过大的内存占用导致内存溢出。如果你是在自己的PC上执行,那么可以使用node --max-old-space-size=8192
来修改内存。但是我需要在Codewars上执行,所以无法修改内存。于是我想的办法是利用尾递归优化。呵呵,Node的尾递归优化?不管了,先试试吧。
- function permutate(str,result) {
- 'use strict';
- let tempArr = [];
- //终止条件str长度为0
- if (str.length == 0) {
- return result
- } else {
- //第一次递归时,插入首字母
- if(result.length === 0){
- tempArr.push(str[0]);
- }else{
- for (let i = 0; i < result.length; i++) {
- let item = result[i];
- let itemLen = item.length;
- for (let j = 0; j < itemLen+1; j++) {
- let temp = item.slice(0, j) + str[0] + item.slice(j);
- tempArr.push(temp);
- }
- }
- }
- //递归截取了第一个字符的子串
- return permutate(str.slice(0),tempArr);
- }
- }
- permutate("abcdefghijkl",[]);
函数的第一个参数是本次递归的字符串,第二个参数是前x个字符的全排列结果。
思路是:
每次取当次递归串的第一个字母;
若第二个参数长度为0说明是第一次递归,则初始化本次结果为[首字母]
。然后将首字母从递归串中剔除,剩余串传给下一次递归;
之后每一次递归,都取递归串的首字母,将其插入前x个字符的全排列的所有位置,求出x+1个字符的全排列;
递归直到第一个参数为空串,则第二个参数为字符串所有字符的全排列。
可能不太好理解,不过知道这是尾递归就行了。虽然尾递归在ES6的严格模式中才有效,但是,我加上'use strict';
后仍然无效。事实上我认为并不是函数调用栈的溢出,而是存放变量的堆溢出。所以,大概是无解了吧。毕竟全排列不管怎么样,空间复杂度都是O(n!)的。
最后再贴个循环的代码吧,也是没什么用,就当扩展思路了。
- function perm(str) {
- let result = [],tempArr = [];
- let subStr = str;
- while (subStr.length !== 0) {
- if (result.length === 0) {
- result.push(str[0]);
- } else {
- for (let i = 0; i < result.length; i++) {
- let item = result[i];
- let itemLen = item.length;
- for (let j = 0; j < itemLen+1; j++) {
- let temp = item.slice(0, j) + subStr[0] + item.slice(j);
- tempArr.push(temp);
- }
- }
- result = tempArr;
- tempArr = [];
- }
- subStr = subStr.slice(1);
- }
- return result;
- }
相关推荐:
JS全排列组合算法实现方法
JavaScript几种递归全排列算法实例详解
JavaScript趣题:全排列去重
以上就是JS关于字符串的全排列算法及内存溢出详解的详细内容,更多请关注Gxl网其它相关文章!