fork download
copy 
  1. import java.util.Arrays;
  2.  
  3. class Main{
  4.   public static void main(String[] args) {
  5.         int n = (int) factorial(4);
  6.         for ( int i = 0; i < n; i++ ) {
  7.           System.out.format( "%d: %s\n", i, Arrays.toString( perm(i, 1, 4 ) ) );
  8.         }
  9.     }
  10.  
  11.  
  12.     /**
  13.        * Returns ith permutation of the n numbers [from, ..., to]
  14.        * (Note that n == to - from + 1).
  15.        * permutations are numbered from 0 to n!-1, if i is outside this
  16.        * range it is treated as i%n! 
  17.        * @param i
  18.        * @param from
  19.        * @param n
  20.        * @return
  21.        */
  22.       public static int[] perm(long i, int from, int to)
  23.       {
  24.         // method specification numbers permutations from 0 to n!-1.
  25.         // If you wanted them numbered from 1 to n!, uncomment this line.
  26.         //  i -= 1;
  27.         int n = to - from + 1;
  28.  
  29.         int[] initArr  = new int[n];             // numbers [from, ..., to]
  30.         int[] finalArr = new int[n];             // permutation of numbers [from, ..., to]
  31.  
  32.         // populate initial array
  33.         for (int k=0; k<n; k++)
  34.           initArr[k] = k+from;
  35.  
  36.         // compute return array, element by element
  37.         for (int k=0; k<n; k++) {
  38.           int index = (int) ((i%factorial(n-k)) / factorial(n-k-1));
  39.  
  40.           // find the index_th element from the initial array, and
  41.           // "remove" it by setting its value to -1
  42.           int m = convertIndex(initArr, index);
  43.           finalArr[k] = initArr[m];
  44.           initArr[m] = -1;
  45.         }
  46.  
  47.         return finalArr;
  48.       }
  49.  
  50.  
  51.       /** 
  52.        * Helper method used by perm.
  53.        * Find the index of the index_th element of arr, when values equal to -1 are skipped.
  54.        * e.g. if arr = [20, 18, -1, 19], then convertIndex(arr, 2) returns 3.
  55.        */
  56.       private static int convertIndex(int[] arr, int index)
  57.       {
  58.         int m=-1;
  59.         while (index>=0) {
  60.           m++;
  61.           if (arr[m] != -1)
  62.             index--;
  63.         }
  64.  
  65.         return m;
  66.       }
  67.  
  68. /** return n!*/
  69.   public static long factorial(int n)
  70.   {
  71.     if (n < 0)
  72.       throw new IllegalArgumentException("factorial not defined for negative numbers: "+n);
  73.     if (n > 20)
  74.       throw new RuntimeException("Cannot calculate "+n+"! - long datatype cannot hold factorials greater than 20!.");
  75.  
  76.     long fact = 1;
  77.     for (int i=n; i>1; i--)
  78.       fact *= i;
  79.  
  80.     return fact;
  81.   }
  82. }
Success #stdin #stdout 0.04s 245632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0: [1, 2, 3, 4]
1: [1, 2, 4, 3]
2: [1, 3, 2, 4]
3: [1, 3, 4, 2]
4: [1, 4, 2, 3]
5: [1, 4, 3, 2]
6: [2, 1, 3, 4]
7: [2, 1, 4, 3]
8: [2, 3, 1, 4]
9: [2, 3, 4, 1]
10: [2, 4, 1, 3]
11: [2, 4, 3, 1]
12: [3, 1, 2, 4]
13: [3, 1, 4, 2]
14: [3, 2, 1, 4]
15: [3, 2, 4, 1]
16: [3, 4, 1, 2]
17: [3, 4, 2, 1]
18: [4, 1, 2, 3]
19: [4, 1, 3, 2]
20: [4, 2, 1, 3]
21: [4, 2, 3, 1]
22: [4, 3, 1, 2]
23: [4, 3, 2, 1]
https://ideone.com/bq35C
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!