output

1 - 5860
1 - 5559
2 - 5870
2 - 2720
3 - 5619
3 - 4459
4 - 19354
4 - 11670
5 - 93840
5 - 49499
6 - 554010
6 - 287005
7 - 9550094
7 - 4766503
8 - 23536082
8 - 12584304
9 - 1756429
9 - 2931610
10 - 38732521
10 - 29251197
11 - 293646345
11 - 322835792
12 - 2275912331
12 - 3900249409
13 - 66186181963
13 - 50382878180

Perm.java

import java.util.*;

class Main {
   public static void swap(int[] arr, int i, int j) {
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
   }

   public static void permuteRecur(int[] arr, int ndx) {
      if (arr.length == ndx+1) {
         //System.out.println(Arrays.toString(arr));
      } else {
         permuteRecur(arr, ndx+1);
         for (int i = ndx+1; i < arr.length; i++) {
            swap(arr, ndx, i);
            permuteRecur(arr, ndx+1);
            swap(arr, ndx, i);
         }
      }
   }

   public static void permute1(int[] a) {
      permuteRecur(a, 0);
   }

   public static void permute2(int[] a) {
      //System.out.println(Arrays.toString(a));
      int n = a.length;
      int[] p = new int[n];  // Index control array initially all zeros
      int i = 1;
      while (i < n) {
         if (p[i] < i) {
            int j = ((i % 2) == 0) ? 0 : p[i];
            swap(a, i, j);
            // Print current
            //System.out.println(Arrays.toString(a));
            p[i]++;
            i = 1;
         }
         else {
            p[i] = 0;
            i++;
         }
      }
   }

   public static void test(int i) {
      long t1,t2;

      int[] arr1 = new int[i], arr2 = new int[i];
      for (int o = 0; o < i; o++)
         arr1[o] = arr2[o] = o;

      t1 = System.nanoTime();
      permute1(arr1);
      t1 = System.nanoTime()-t1;
      System.out.println(i+" - "+t1);

      t2 = System.nanoTime();
      permute2(arr2);
      t2 = System.nanoTime()-t2;
      System.out.println(i+" - "+t2);
   }

   public static void main(String[] args) {
      for (int i=1; i < 14; i++)
         test(i);
   }
}