algorithm - 此字符串排列如何工作

需要帮助理解第二个交换调用的正确性。

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
       for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); // how does this work here?
       }
   }
}

似乎第二次交换是撤销第一次交换但我看不出为什么中间的permute调用会保留原来的*(a+i)将保持在a+j的证据。
笔记：
[1]在http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

最佳答案

命题：对于长度a的所有> n（因此n是一个有效的指标）和0 <= i <= n，当

permute(a, i, n)

返回，a与调用permute时相同。
证明：（归纳开始）如果i == n，那么permute(a, n, n);只打印字符串而不更改它，因此在这种情况下命题成立。
（归纳假设）设0 <= k < n，命题的enoncé适用于所有k < i <= n。
然后在循环中

for (j = i; j <= n; j++)
{
    swap((a+i), (a+j));
    permute(a, i+1, n);
    swap((a+i), (a+j)); // how does this work here?
}

对于每个j，对permute的递归调用不会根据假设更改内容[更准确地说，它会撤消中间完成的所有更改]因此，在第二个swap之前，a[i]和a[j]的内容正是第一个交换之后的内容，因此在循环体的末尾，a的内容正是进入循环体时的内容。

关于algorithm - 此字符串排列如何工作，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16550499/