title: How Does This String Permutation Works
body: <p>Need help understanding the correctness of the second swap call.</p>
  
  <pre><code>/* 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 &lt;= n; j++)
         {
            swap((a+i), (a+j));
            permute(a, i+1, n);
            swap((a+i), (a+j)); // how does this work here?
         }
     }
  }
  </code></pre>
  
  <p>It seems like the second swap is to undo the first swap. But I don't see a proof why the in-between <code>permute</code> call would preserve that the original <code>*(a+i)</code> would remain at <code>a+j</code>.</p>
  
  <p>Notes:</p>
  
  <p>[1] Code was found at <a href="http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/" rel="nofollow">http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/</a></p>