title: Go through all permutations of an array recursively
body: <p>I am trying to write a recursive function to produce all permutations of an array.</p>
  
  <pre><code>static int permus[] = new int[] { 1, 2, 3, 4, 5 };
  
  
  static void testPermu(int start)
  {
      // Print it
      System.out.println(Arrays.toString(permus));
  
      int k;
      for (int i = start + 1; i &lt; permus.length; i++) {
          // swap
          k = permus[start];
          permus[start] = permus[i];
          permus[i] = k;
  
          testPermu(i);
  
          // unswap
          k = permus[start];
          permus[start] = permus[i];
          permus[i] = k;
      }
  }
  </code></pre>
  
  <p>It's invoked as <code>testPermu(0)</code> and should produce all permutations, however that does not work. How can I fix it?</p>
  
  <p>It needs to be recursive, each time the function is invoked, it should get a fresh permutation.</p>
  
  <p>output now is </p>
  
  <pre>
  [1, 2, 3, 4, 5]
  [2, 1, 3, 4, 5]
  [2, 3, 1, 4, 5]
  [2, 3, 4, 1, 5]
  [2, 3, 4, 5, 1]
  [2, 3, 5, 4, 1]
  [2, 4, 3, 1, 5]
  [2, 4, 3, 5, 1]
  [2, 5, 3, 4, 1]
  [3, 2, 1, 4, 5]
  [3, 2, 4, 1, 5]
  [3, 2, 4, 5, 1]
  [3, 2, 5, 4, 1]
  [4, 2, 3, 1, 5]
  [4, 2, 3, 5, 1]
  [5, 2, 3, 4, 1]
  </pre>
  
  <p>You can see that many of the permutations are missing.</p>
  
  <p>I'm writing it in Java but I'll understand example in C, javascript or anything else as long as it's not using some library tricks not available in Java.</p>