import java.util.Arrays;

class Main{
  public static void main(String[] args) {
        int n = (int) factorial(4);
        for ( int i = 0; i < n; i++ ) {
          System.out.format( "%d: %s\n", i, Arrays.toString( perm(i, 1, 4 ) ) );
        }
    }


    /**
       * Returns ith permutation of the n numbers [from, ..., to]
       * (Note that n == to - from + 1).
       * permutations are numbered from 0 to n!-1, if i is outside this
       * range it is treated as i%n! 
       * @param i
       * @param from
       * @param n
       * @return
       */
      public static int[] perm(long i, int from, int to)
      {
        // method specification numbers permutations from 0 to n!-1.
        // If you wanted them numbered from 1 to n!, uncomment this line.
        //  i -= 1;
        int n = to - from + 1;
    
        int[] initArr  = new int[n];             // numbers [from, ..., to]
        int[] finalArr = new int[n];             // permutation of numbers [from, ..., to]
    
        // populate initial array
        for (int k=0; k<n; k++)
          initArr[k] = k+from;
    
        // compute return array, element by element
        for (int k=0; k<n; k++) {
          int index = (int) ((i%factorial(n-k)) / factorial(n-k-1));
    
          // find the index_th element from the initial array, and
          // "remove" it by setting its value to -1
          int m = convertIndex(initArr, index);
          finalArr[k] = initArr[m];
          initArr[m] = -1;
        }
    
        return finalArr;
      }
      
    
      /** 
       * Helper method used by perm.
       * Find the index of the index_th element of arr, when values equal to -1 are skipped.
       * e.g. if arr = [20, 18, -1, 19], then convertIndex(arr, 2) returns 3.
       */
      private static int convertIndex(int[] arr, int index)
      {
        int m=-1;
        while (index>=0) {
          m++;
          if (arr[m] != -1)
            index--;
        }
    
        return m;
      }

/** return n!*/
  public static long factorial(int n)
  {
    if (n < 0)
      throw new IllegalArgumentException("factorial not defined for negative numbers: "+n);
    if (n > 20)
      throw new RuntimeException("Cannot calculate "+n+"! - long datatype cannot hold factorials greater than 20!.");

    long fact = 1;
    for (int i=n; i>1; i--)
      fact *= i;

    return fact;
  }
}