递归打印字符串的所有排列 (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

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

  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("abcabad".split('')))
.map(perm => perm.join(''))
.filter((el, idx, self) => (self.indexOf(el) === idx)));

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').filter((el, idx, self) => (self.indexOf(el) === idx));
    console.log("Total permutation: "+permutation.length);
    console.log(permutation);

Answer 4

半题：

给定字符串的随机排列就像 rndperm:

一样简单

i = document.getElementById("word");
b = document.getElementById("butt");

rndperm = (z) => {
  return z.split("").sort(() => ((Math.random() * 3) >> 0) - 1).join("")
}

function scramble() {
  i.value = rndperm(i.value);
}

var z;

function sci() {
  if (z != undefined) {
    clearInterval(z);
    b.innerText = "Scramble";
    z=undefined;
  } else {
    z = setInterval(scramble, 100);
    b.innerText = "Running...";
  }
}

<center><input id="word" value="HelloWorld"></input><button id="butt" onclick=sci()>Scramble</button></center>

Answer 5

问题分类：你可以把这个问题看成一个探索问题，即给定一组输入字符，探索你可以排列它们的不同方式。

解法： Backtracking算法虽然时间复杂度高，但擅长解决探索性问题。为了演示解决方案，想象一下您将如何针对一小组输入字符手动解决此问题：[a, b, c]。

步骤如下：

取最左边的字符。这是索引 0 处的字符，并将其与索引 0 处的目标右字符交换，即与其自身交换。这是因为 [a, b, c] 本身就是一个有效的排列，因此我们希望保留它。交换字符通常需要两个指向每个字符的指针。所以假设我们将有一个 left 和 right 指针。
用最左边的相同字符（在索引 0 处）与索引 0 + 1 = 1 处的目标右字符进行交换，即将目标右指针进一步移动 1 步。这将为您提供输出：[b, a, c]
使用最左边的相同字符（在索引 0 处）与下一个目标右侧字符（即索引 0 + 1 + 1 = 2）进行交换。这将为您提供输出：[c, b, a]
好的，现在我们需要停止，因为没有更多的目标右侧字符要与最左侧的字符交换。所以我们的 right 指针需要保持小于 input 中的最大索引。一次移动 right 指针一步，我们可以使用从 left[=81] 开始的 for 循环=] 索引并以输入长度 - 1 结尾。

现在您需要执行与上面完全相同的步骤，但移动左指针使其指向下一个最左边的字符。但是，保留步骤 2 和 3 的输入。另一种想象这种情况的方法是：'Hey, I am done with the left most character. Now I do not want to work with it anymore but I would love to continue with the second left most from the results I have so far.'

我们什么时候停止？当左指针达到输入字符串的长度 - 1 时，因为在这个索引之后没有更多的字符。在递归算法（如回溯）中，需要停止的情况称为base case。在我们的示例中，基本情况是：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]

总结：

要将 left 指针向右移动，我们将使用递归增量

要将 right 指针向右移动，我们将使用 for 循环，但是我们需要始终从左指针开始否则我们将探索我们已经探索过的东西。

回溯： 回溯算法的伪代码采用以下形式：

fun(input) if(base_case_check(input)) { //do final step } else { //choose fun(reduce(input)) //explore //un-choose }

我们的解决方案：

function permutate(string) { if(!string || string.length === 0) return new Set(['']); let left = 0; let result = new Set(); permutationHelper(string, result, left); return result; } function permutationHelper(string, result, left) { if(left === string.length-1) { //base case result.add(string); } else { //recursive case for(let right=left; right < string.length; right++) { string = swap(string, left, right); //choose permutationHelper(string, result, left+1); // explore string = swap(string, left, right); //unchoose } } } function swap(string, left, right) { let tmpString = string.split(''); let tmp = tmpString[left]; tmpString[left] = tmpString[right]; tmpString[right] = tmp; return tmpString.join(''); } /* End of solution */ /* Tests */ let input = 'abc'; let result = permutate(input); let expected = new Set(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']); if(setsEquality(result, expected)) { console.log('Congrats, you generated all permuations'); } else { console.log('Sorry, not all permuations are generated'); } function setsEquality(actualResult, expectedResult) { if (actualResult.size !== expectedResult.size) { return false; } for (let permutation of actualResult) { if (!expectedResult.has(permutation)) return false; } return true; } function assert(condition, desc) { if (condition) { console.log(`${desc} ... PASS`); } else { console.log(`${desc} ... FAIL`); } }

总结和时间复杂度：

我们通过交换现有输入字符串中的字符来做出选择

一旦我们将左索引递增 1，我们就会探索剩下有待探索的内容。这实际上意味着我们正在将所有后续递归的输入集减少为 1。因此，我们需要做的工作是：Nx(N-1)x(N-2)x(N-3)x...x1 = N!。但是，由于我们需要一个 for 循环来探索我们拥有的输入，因此总时间复杂度为：0(N*N!)

我们通过在修改后的输入字符串中交换字符来恢复我们的选择

Answer 6

permutation=(str,prefix)=>{
   if(str.length==0){
      console.log(prefix);
   }
   else{
      for(let i=0;i<str.length;i++){
          let rem = str.substring(0,i)+str.substring(i+1);
          permutation(rem,prefix+str[i]);
       }
    }
 }
 let str="ABC";
 permutation(str,"");

Answer 7

我的面试官昨天也问了我同样的问题，但我没有得到正确的逻辑然后我来到 Whosebug 我到了这里，但现在我有了我的解决方案并想与所有人分享

const str_Permutations = (str,ar = []) => {
  str = `${str}`; // ensure type **String**
  if(ar.indexOf(str)>-1 || str.length !== (ar.strlen || str.length)) return false; // Checking if value is alreay there or(||) on recursive call string length should not be provided string 
  ar.strlen = ar.strlen || str.length; // Setting str length of provided value(string)
  ar.push(str);    // Pushing to array
  for(let i = 0; i<str.length;i++){
    str_Permutations(str[i] + str.split('').filter(v=>v!==str[i]).join(''),ar);
  }
  return Array.from(ar); // Removing *strlen* from main result and return **Result** as array
}
str_Permutations("ABC")

//Result: (6) ["ABC", "BAC", "CBA", "BCA", "ACB", "CAB"]

使用了 Array 的引用特性来通过传递将值保存在相同的 Array 中。我希望你明白我的意思！！！！

Answer 8

var str = "abcdefgh";

for(let i = 0; i<str.length; i++){
    for(let j = i; j<=str.length; j++){
        if(i != j){
            var out = str.slice(i,j);
        console.log(out);
        }
        
    }
}

Answer 9

const permut = (str) => {
  if (str.length <= 2) return str.length === 2 ? [str, str[1] + str[0]] : [str];
  return str
    .split("")
    .reduce(
      (acc, letter, i) =>
        acc.concat(
          permut(str.slice(0, i) + str.slice(i + 1)).map((val) => letter + val)
        ),
      []
    );
};

找到here

递归打印字符串的所有排列 (Javascript)

Recursively print all permutations of a string (Javascript)

javascript

string

algorithm

recursion

permutation