2

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

/* 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-ac-program-to-print-all-permutations-of-a-given-string/

4

1 回答 1

3

命题：对于所有a的长度> n（所以这n是一个有效的索引）并且0 <= i <= n，当

permute(a, i, n)

返回，与调用a时相同。permute

证明：（归纳开始）如果i == n，则permute(a, n, n);仅打印字符串而不更改它，因此该命题在这种情况下成立。

（归纳假设）让0 <= k < n, 和命题的 enncé 对所有人都成立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?
}

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

于 2013-05-14T19:10:49.363 回答