該字符串排列如何工作

需要幫助瞭解第二個交換呼叫的正確性。該字符串排列如何工作

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

來源

2013-05-14 kirakun

你給這個代碼手工運行嗎？ – BlackVegetable

通過歸納證明它。「i == n-1」顯然是正確的。如果某個'0

@BlackVegetable。我做了同樣的事情：添加printf。而且這表明確實這個'permute'調用似乎在調用之前和之後保留了'a'。現在，我無法證明爲什麼。 – kirakun

命題發現：對於長度> n的所有a（使得n是有效的索引）和0 <= i <= n，當

permute(a, i, n)

返回，a與調用permute時相同。

證明：（感應啓動）如果i == n，然後permute(a, n, n);只打印字符串，並不會改變它，因此主張在這種情況下成立。

（誘導假設）令0 <= k < n，並且該命題的參數適用於所有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的內容正是它們在輸入循環體時的內容。

來源

2013-05-14 19:10:49

該字符串排列如何工作

回答

相關問題