algorithm - How Does This String Permutation Works -

need understanding correctness of second swap call.

/* function print permutations of string    function takes 3 parameters:    1. string    2. starting index of string    3. ending index of string. */ void permute(char *a, int i, int n)  {    int j;     if (i == n)      printf("%s\n", a);    else    {        (j = i; j <= n; j++)        {           swap((a+i), (a+j));           permute(a, i+1, n);           swap((a+i), (a+j)); // how work here?        }    } } 

it seems second swap undo first swap. don't see proof why in-between permute call preserve original *(a+i) remain @ a+j.

notes:

[1] code found @ http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

proposition: a of length > n (so n valid index) , 0 <= <= n, when

permute(a, i, n) 

returns, a same when permute called.

proof: (induction start) if i == n, permute(a, n, n); prints string , doesn't change it, hence proposition holds in case.

(induction hypothesis) let 0 <= k < n, , enoncé of proposition hold k < <= n.

then in loop

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

for each j, recursive call permute doesn't change contents [more precisely, undoes changes intermediately done] per hypothesis. therefore, before second swap, contents of a[i] , a[j] after first swap, hence @ end of loop body, contents of a when loop body entered.