递归打印字符串的所有排列（Javascript）

一尘不染

递归打印字符串的所有排列（Javascript）

algorithm

我见过针对其他语言的此问题版本，但对于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?
       } 
    }
}

阅读 292

2020-07-28

共1个答案

一尘不染

让我们编写一个函数，将一个字符串的所有排列作为数组返回。由于您不需要任何全局变量，因此返回排列至关重要。

  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

希望我能帮助您解决您的问题。

2020-07-28