import java.util.Arrays; class Main{ int n = (int) factorial(4); for ( int i = 0; i < n; i++ ) { } } /** * 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) 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; } }
Standard input is empty
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]