javascript - 堆的算法置换 JavaScript 和递归的堆栈？

Question

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

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"]

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

Answer 1

不知道你说的是什么

understand recursion within this code in a loop

如果你的意思是你想以循环形式而不是递归形式查看算法，你可以在 wikipedia page here 中的伪代码中并排查看它们。 .

对于代码中的问题:

how does this loop executes within the call stack?

你提到调用堆栈是对的，这是关于递归的一般问题。如果您不了解递归如何与堆栈一起工作，您可以引用 this really nice and simple video演示了在 Java 中使用阶乘计算的递归调用(大约从 4:00 分开始)。

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

i don't understand this part. i understand the swap function, but I don't get how indexes are swapped here

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

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

只是

swap(a, b);

与

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

如果a部分让你感到困惑，那么这是对 the ternary operator for conditional value 的使用.也就是说，它是用来形成一个表达式的符号，根据情况进行不同的评估。使用是通过

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

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

在代码本身中，对于 a , n % 2是 bool 表达式 - js 除 n通过 2并拿走余数。余数是 1或 0 . js 将这些隐式转换为 true和 false分别。所以如果n很奇怪我们得到

a = 0

如果它是偶数我们得到

a = i

根据算法要求。