// FactPermutes.java // Aiswarya Prakasan, Feb. 2017 // https://medium.com/@aiswaryamathur/find-the-n-th-permutation-of-an-ordered-string-using-factorial-number-system-9c81e34ab0c8 // Modified by Andrew Davison, ad@coe.psu.ac.th, Dec. 2022 /* This program is a standalone example of coding permutations using the Factoradic number system. https://en.wikipedia.org/wiki/Factorial_number_system The end result is the function WordUtils.fpermute() which is used to generate permutations in Anagrams.java. --- The central idea of the Factoradic number system is that it's possible to calculate permutations incrementally rather than all at once using a recursive or iterative algorithm. This means that there's no need to utilize a large list to store all the permutations, which may well run out of heap space (which actually happpened in Anagrams.java before the code change). --- A string of n characters will generate n! permutations. The factoradic representation allows a number i (between 0 and n!-1) to be mapped to the corresponding ith permutation. For example, here are the permutations of the string "abcd" shown with an increasing n value 0 to 4!-1 (23) 0 abcd 6 bacd 12 cabd 18 dabc 1 abdc 7 badc 13 cadb 19 dacb 2 acbd 8 bcad 14 cbad 20 dbac 3 acdb 9 bcda 15 cbda 21 dbca 4 adbc 10 bdac 16 cdab 22 dcab 5 adcb 11 bdca 17 cdba 23 dcba There is a pattern to the letters: * the first letter changes after every 6th (3!) permutation * the second letter changes after 2(2!) permutation * the third letter changed after every (1!) permutation, and * the fourth letter changes after every (0!) permutation The numbers beside each permutation can be converted to the factoradic number system. Successively divide the number by 1,2,3,4 and so on until the quotient becomes zero, and store the remainders in right-to-left order in an array. e.g. the factoradic version of 17 == [2, 2, 1, 0] because 17/1 -> 17/2 -> 8/3 -> 2/4 quotient: 17 8 2 0 remainder: 0 1 2 2 The digits in the factoradic array can now be used to lookup the letters of the corresponding permutation. Assume that the original string, "abcd" is stored in a LETTERS array like so: [a, b, c, d] For each digit in the factoradic array, add the character from that position in LETTERS to the required permutation. Count from the left, starting at 0, and only use unused letters. e.g. [2, 2, 1, 0] applied to [a, b, c, d] produces "cdba" 0 1 2 3 "cdba" is the 17th permutation, as shown above. Usage: > compile FactPermutes.java > run FactPermutes n e.g. > run FactPermutes 17 Factoradic version of 17: [2, 2, 1, 0] The 17th permutation of "abcd" is "cdba" */ import java.util.*; public class FactPermutes { private static final char[] LETTERS = { 'a', 'b', 'c', 'd' }; /* LETTERS represent the characters in the original string that is to be permuted. So, the current array represents "abcd" */ public static void main(String[] args) { if (args.length != 1) { System.out.println("Usage: java FactPermutes n"); return; } long n = WordUtils.getLong(args[0]); long maxN = factorial(LETTERS.length); if (n > maxN-1) { // must be between 0 and n!-1 System.out.println("Number is too large; should be < " + maxN); System.exit(1); } int[] factd = getFactoradic(n, LETTERS); System.out.println("Factoradic version of " + n + ":\n" + Arrays.toString(factd)); String perm = getPermutation(factd, LETTERS); System.out.println("The " + n + "th permutation of \"" + new String(LETTERS) + "\" is \"" + perm + "\""); } /* main */ private static long factorial(int f) /* I've used long here rather than int, so that factorial can handle values up to 20. The int type can only deal with a maximum value of 12. factorial(13) is bigger than 2^32, factorial(21) is bigger than 2^64 */ { if (f == 0) return 1L; else return f*factorial(f-1); } private static int[] getFactoradic(long n, char[] letters) /* Generate the factoradic representation of n. Successively divide the number by 1,2,3,4 and so on until the quotient becomes zero, and store the remainders in right-to-left order in factd[]. */ { int[] factd = new int[letters.length]; long idx = 1L; while (n != 0) { factd[(int)(letters.length - idx)] = (int)(n%idx); n = n/idx; idx++; } return factd; } /* getFactoradic */ private static String getPermutation(int[] factd, char[] letters) /* Generate the nth permutation of letters by using the Factoradic representation of n */ { ArrayList permChs = new ArrayList<>(); boolean[] isCharUsed = new boolean[letters.length]; // by default, values are initialised to false for (int i = 0; i < factd.length; i++) { int pos = factd[i]; char ch = getUnusedCharAtPos(pos, isCharUsed, letters); permChs.add(ch); } StringBuilder sb = new StringBuilder(); for (char ch : permChs) sb.append(ch); return sb.toString(); } /* getPermutation */ private static char getUnusedCharAtPos(int pos, boolean[] isCharUsed, char[] letters) /* Return the character from pos in letters. Count from the left, starting at 0, and only count unused letters. */ { int unusedCnt = -1; for (int i = 0; i < letters.length; i++) { if (!isCharUsed[i]) { unusedCnt++; if (unusedCnt == pos) { isCharUsed[i] = true; return letters[i]; } } } System.out.println("No unused character at " + pos); return '?'; } /* getUnusedCharAtPos */ } // end of FactPermutes class