algorithm - 这个字符串排列是如何工作的

Question

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

/* 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/

Answer 1

命题:对于所有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 的内容正是进入循环体时的状态。