摘要：问题给定字符串，求出所有由该串内字符组合的全排列。于是我想的办法是利用尾递归优化。算法二尾递归终止条件长度为第一次递归时，插入首字母递归截取了第一个字符的子串函数的第一个参数是本次递归的字符串，第二个参数是前个字符的全排列结果。
问题
给定字符串，求出所有由该串内字符组合的全排列。所包含的字符不重复。
输入："abc" 输出：["abc","acb","bac","bca","cab","cba"]
我在实现算法时遇到了一个问题，至今无法解决。但是全排列算法又很重要，所以写这篇文章记录一下。
算法一：递归算法思想：
当字符串长度为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;
}
总结
第一次遇到解决不了的问题啊，感觉很不开心。我还特地跑到stackoverflow上问了，然后回答的都不能解决。所以我也只好放弃了，真是不甘心。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/93014.html
摘要：本文详细描述了堆内存模型，垃圾回收算法以及处理内存泄露的最佳方案，并辅之以图表，希望能对理解内存结构有所帮助。该区域也称为内存模型的本地区。在中，内存泄露是指对象已不再使用，但垃圾回收未能将他们视做不使用对象予以回收。 本文详细描述了 Java 堆内存模型，垃圾回收算法以及处理内存泄露的最佳方案，并辅之以图表，希望能对理解 Java 内存结构有所帮助。原文作者 Sumith Puri，...
摘要：结构型模式适配器模式桥接模式装饰模式组合模式外观模式享元模式代理模式。行为型模式模版方法模式命令模式迭代器模式观察者模式中介者模式备忘录模式解释器模式模式状态模式策略模式职责链模式责任链模式访问者模式。 主要版本 更新时间 备注 v1.0 2015-08-01 首次发布 v1.1 2018-03-12 增加新技术知识、完善知识体系 v2.0 2019-02-19 结构...
摘要：导读阅读本文需要有足够的时间，笔者会由浅到深带你一步一步了解一个资深架构师所要掌握的各类知识点，你也可以按照文章中所列的知识体系对比自身，对自己进行查漏补缺，觉得本文对你有帮助的话，可以点赞关注一下。目录一基础篇二进阶篇三高级篇四架构篇五扩 导读：阅读本文需要有足够的时间，笔者会由浅到深带你一步一步了解一个资深架构师所要掌握的各类知识点，你也可以按照文章中所列的知识体系对比自身，对自己...
摘要：就是说引用计数法很难解决对象之间的相互引用问题也无法通知回收器去及时回收它。因为存在这种缺点，所以现在的虚拟机基本上并不是通过引用计数法来判断对象是否存活。 1、为什么要进行垃圾回收？ 每当在我们写代码的时候，不管是new一个对象，还是引用，还是填充数据到数组，都是要占用空间，那么如果不及时回收就会对系统的运行产生影响。java和c 一个很大的区别就在于，java的垃圾回收主要是jv...
阅读 3083·2021-10-14 09:42
阅读 3536·2019-08-26 13:56
阅读 3368·2019-08-26 11:59
阅读 870·2019-08-23 18:00
阅读 2099·2019-08-23 17:51
阅读 3500·2019-08-23 17:17
阅读 1459·2019-08-23 15:11
阅读 5054·2019-08-23 15:05
