1

我有一个任务是根据堆的算法排列来计算重复的字符串。我要做的第一件事是输出交换的字符串，我从jake 的回答中找到了这段代码，有人可以帮我理解循环中这段代码中的递归吗？此函数的输出是交换的字符串。

function permAlone(string) {

var arr = string.split(''),   // Turns the input string into a letter array.
          permutations = []; // results

function swap(a, b) {  
debugger; // This function will simply swap positions a and b inside the input array.
var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}

function gen(n) {   
  debugger;
  if (n === 1) {  
  var x =arr.join('');
  permutations.push(x);  
  } else {
  for (var i = 0; i != n; i++) { // how does this loop executes within the call stack?  
    gen(n - 1);
    debugger;
    swap(n % 2 ? 0 : i, n - 1); // i don't understand this part. i understand the swap function, but I don't get how indexes are swapped here
  }   
 }
}
 gen(arr.length);
 return permutations;
}
permAlone('xyz'); // output -> ["xyz","yxz","zxy","xzy","yzx","zyx"]

我一直在调试器上对其进行试验，但仍然无法了解发生了什么。

4

1 回答 1

3

我不确定你的意思

在循环中理解此代码中的递归

如果您的意思是您想以循环形式而不是递归版本来查看算法，您可以在此处的维基百科页面中以伪代码并排查看它们。

对于代码中的问题：

这个循环如何在调用堆栈中执行？

您参考调用堆栈是正确的，这是关于递归的一般问题。如果您不了解递归如何与堆栈一起工作，您可以参考这个非常漂亮且简单的视频，该视频演示了在 java 中使用阶乘计算进行递归调用（从 4:00 左右开始）。

您看到的行与递归函数中的任何其他行没有什么不同。我们首先定义 i 并将值 0 分配给它。我们继续检查它是否满足for循环的条件。如果是，我们进入循环并执行循环内的第一行，即递归调用。在递归调用内部，我们有一个新的堆栈框架，它不知道我们在执行递归调用之前定义的 i 变量，因为它是一个局部变量。因此，当我们在新调用中进入循环时，我们定义了一个新变量 i，首先将其分配为 0，并随着循环在此堆栈帧/调用实例中重复而递增。当这个调用完成时，我们删除堆栈帧并恢复到 i=0 的前一个堆栈帧（我们开始的那个），然后我们继续下一行。所有调用都可以访问 arr 和 permutations 变量，因为该函数与变量定义在同一范围内（在函数 permAlone 中），因此在每次调用中 - 无论我们在什么堆栈框架中，对这些变量所做的更改都是制作相同的实例。这就是为什么对排列所做的每次推送都会添加到现有结果中，并且会在函数最后返回变量时出现。

我不明白这部分。我了解交换功能，但我不明白如何在这里交换索引

此处不交换索引。它只是调用具有正确索引的交换函数。

swap(n % 2 ? 0 : i, n - 1);

只是

swap(a, b);

和

a = n% 2 ? 0 : i;
b = n - 1;

如果这a部分让您感到困惑，那么这是对条件值的三元运算符的使用。也就是说，它是用于形成表达式的符号，该表达式根据情况进行不同的评估。用途是由

<<i>boolean epression</i>> ? <<i>value-if-true</i>> : <<i>value-if-false</i>>

要评估上述内容，首先要评估 < boolean expression >。如果它是值，true则整个表达式被评估为 < value-if-true >。否则，整个表达式被评估为 < value-if-false >。

在代码本身中， fora是n % 2布尔表达式 - js 除以n并2取余数。余数为1或0。Node.js 隐式地将它们分别转换为true和false。所以如果n是奇怪的我们得到

a = 0

如果它甚至我们得到

a = i

按照算法的要求。

于 2016-09-09T15:53:44.260 回答