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

Question

我已经看到了其他语言的这个问题的版本，但不是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?
       } 
    }
}

Answer 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

希望我能帮助你解决问题。

Answer 2

已经研究了排列问题以致死亡。 Heap's algorithm是一个众所周知的解决方案。这是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("xyz".split(''))).map(perm => perm.join('')));

permute用于获取和生成数组，而不是字符串，因此我们在调用之前将字符串拆分为字符，然后在打印出结果之前将字符粘贴回字符串。

Answer 3

使用递归函数迭代字符串

    

    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');
    console.log("Total permutation: "+permutation.length);
    console.log(permutation);