sin*_*tor 28 javascript string algorithm recursion permutation
我已经看到了其他语言的这个问题的版本,但不是JS.
是否可以在一个函数中递归执行此操作？
我理解我需要获取字符串中的第一个元素,然后将其附加到每个解决方案中,以便对字符串的其余部分进行递归.从逻辑上讲,我理解递归是如何进行的.我只是不明白如何将第一个字符串附加到每个递归解决方案上
var myString = "xyz";
function printPermut(inputString){
var outputString;
if(inputString.length === 0){
return inputString;
}
if(inputString.length === 1){
return inputString;
}
else{
for(int i = 0; i<inputString.length(); i++){
//something here like:
//outputString = outputString.concat(printPermut(inputString.slice(1))??
//maybe store each unique permutation to an array or something?
}
}
}
小智 59
让我们编写一个函数,将字符串的所有排列作为数组返回.由于您不需要任何全局变量,因此返回排列至关重要.
function permut(string) {
if (string.length < 2) return string; // This is our break condition
var permutations = []; // This array will hold our permutations
for (var i=0; i<string.length; i++) {
var char = string[i];
// Cause we don't want any duplicates:
if (string.indexOf(char) != i) // if char was used already
continue; // skip it this time
var remainingString = string.slice(0,i) + string.slice(i+1,string.length); //Note: you can concat Strings via '+' in JS
for (var subPermutation of permut(remainingString))
permutations.push(char + subPermutation)
}
return permutations;
}
要打印它们,之后只需迭代数组:
var myString = "xyz";
permutations = permut(myString);
for (permutation of permutations)
print(permutation) //Use the output method of your choice
希望我能帮助你解决问题.
小智 40
已经研究了排列问题以致死亡.Heap的算法是一个众所周知的解决方案.这是JS中的一个版本,使用了一个生成器:
function *permute(a, n = a.length) {
if (n <= 1) yield a.slice();
else for (let i = 0; i < n; i++) {
yield *permute(a, n - 1);
const j = n % 2 ? 0 : i;
[a[n-1], a[j]] = [a[j], a[n-1]];
}
}
console.log(Array.from(permute("abcabad".split('')))
.map(perm => perm.join(''))
.filter((el, idx, self) => (self.indexOf(el) === idx)));permute 旨在利用并产生数组,而不是字符串,所以我们叫它之前分割字符串转换成字符,打印出结果之前的字符粘贴到字符串.
使用递归函数迭代字符串
function getPermutations(string) {
var results = [];
if (string.length === 1)
{
results.push(string);
return results;
}
for (var i = 0; i < string.length; i++)
{
var firstChar = string[i];
var otherChar = string.substring(0, i) + string.substring(i + 1);
var otherPermutations = getPermutations(otherChar);
for (var j = 0; j < otherPermutations.length; j++) {
results.push(firstChar + otherPermutations[j]);
}
}
return results;
}
var permutation = getPermutations('YES').filter((el, idx, self) => (self.indexOf(el) === idx));
console.log("Total permutation: "+permutation.length);
console.log(permutation);问题分类：您可以将此问题视为探索问题，即给定一组输入字符，探索可以排列它们的不同方式。
解决方案： 回溯算法在解决探索性问题方面表现出色，但时间复杂度较高。为了演示解决方案，想象一下如何针对一小组输入字符手动解决此问题：[a, b, c]。
步骤如下：
好的，现在我们需要停止，因为没有更多的目标右侧字符可以与最左边的字符交换。因此，我们的右指针需要保持小于输入中的最大索引。我们可以使用for循环来一次移动右指针一步，该循环从左索引开始，以输入长度 - 1 结束。
现在您需要执行与上面完全相同的步骤，但移动左侧指针，使其指向下一个最左边的字符。但是，保留步骤 2 和 3 中的输入。想象这种情况的另一种方式是说：“嘿，我已经完成了最左边的字符。” 现在我不想再使用它，但我很乐意继续使用迄今为止的结果中最左边的第二个。
我们什么时候停下来？当左指针达到输入字符串的长度 - 1 时，因为该索引之后没有更多字符。在递归算法（例如回溯）中，需要停止的情况称为基本情况。在我们的示例中，基本情况是：left === input.length - 1。
这是一个图形可视化：
left index| Input String:
-------------------------------------------------------------------------------
left = 0 | in=[a, b, c]
(swap in[0] with in[0]) (swap in[0] with in[1]) (swap in[0] with in[2])
left = 1 | in=[a, b, c] in=[b, a, c] in=[c, b, a]
(swap in[1] with in[1]) (swap in[1] with in[2]) (swap in[1] with in[1])(swap in[1] with in[2]) (swap in[1] with in[1])(swap in[1] with in[2])
left = 2 | [a, b, c] [a, c, b] [b, a, c] [b, c, a] [c, b, a] [c, a, b]
概括：
回溯： 回溯算法的伪代码采用以下形式：
fun(input)
if(base_case_check(input)) {
//do final step
} else {
//choose
fun(reduce(input)) //explore
//un-choose
}
我们的解决方案：
left index| Input String:
-------------------------------------------------------------------------------
left = 0 | in=[a, b, c]
(swap in[0] with in[0]) (swap in[0] with in[1]) (swap in[0] with in[2])
left = 1 | in=[a, b, c] in=[b, a, c] in=[c, b, a]
(swap in[1] with in[1]) (swap in[1] with in[2]) (swap in[1] with in[1])(swap in[1] with in[2]) (swap in[1] with in[1])(swap in[1] with in[2])
left = 2 | [a, b, c] [a, c, b] [b, a, c] [b, c, a] [c, b, a] [c, a, b]
摘要和时间复杂度：