Finding Kth Permutation Sequence

Question

I have written a program to display the kth permutation sequence of a string made up of letters 'O' and 'Z' . I tried optimizing it but my code have not passed test cases due to timeout issues.Looking for someone who can guide me in optimizing the code i posted below.

public static void main(String[] args) throws IOException {
 /*
 * Sample Input 
 * 1 
 * 3 2 // Passing two inputs as single string
 * 
 * Sample Output
 * OOZ
 */
 // Scanner in = new Scanner(System.in);
 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 String line = br.readLine();
 // Getting 2 integer inputs with space
 String[] k1 = br.readLine().split("\\s");
 // String b1 = br.readLine();
 String eol = System.getProperty("line.separator");
 // byte[] eolb = eol.getBytes();
 long t = Integer.parseInt(line);
 long k = Integer.parseInt(k1[0]);
 long b = Integer.parseInt(k1[1]);
 char set1[] = { 'O', 'Z' };
 ArrayList<String> prefixlist = new ArrayList<String>();
 printAllKLength(set1, k, prefixlist, b);
}
static void printAllKLength(char set[], long k,
 ArrayList<String> prefixlist, long b) throws IOException {
 int n = set.length;
 BufferedOutputStream bout = new BufferedOutputStream(System.out);
 printAllKLengthRec(set, "", n, k, prefixlist);
 Collections.sort(prefixlist);
 if (b <= prefixlist.size()
 && prefixlist.contains(prefixlist.get((int) (b + 1)))) {
 byte b1[] = String.valueOf(prefixlist.get((int) (b - 1)))
 .getBytes();
 bout.write(b1);
 bout.write(System.lineSeparator().getBytes());
 bout.flush();
 // System.out.println(prefixlist.get((int) (b - 1)));
 } else {
 byte b1[] = "-1".getBytes();
 bout.write(b1);
 bout.write(System.lineSeparator().getBytes());
 bout.flush();
 }
}
static void printAllKLengthRec(char set[], String prefix, int n, long k,
 ArrayList<String> prefixlist) {
 if (k == 0) {
 if (!prefix.contains("ZZ")) {
 prefixlist.add(prefix);
 }
 return;
 }
 for (int i = 0; i < n; ++i) {
 String newPrefix = prefix + set[i];
 printAllKLengthRec(set, newPrefix, n, k - 1, prefixlist);
 }
}

• Zack: Can you provide a few text examples of the input and output?
• codeX: 1 3 2 // Passing two inputs as single string input. Output: OOZ //I have provided this sample input format at the starting of the program

Answer 1

You are hitting the time limit as you are supposed to only find the k-th permutation, but you are generating all permutations instead. Look at this discussion. You will probably have to replace the term (numberOfCharacters!) with (numberOfCharacters!/countO!/countZ!) as explained here.

• DarthGizka: Executive summary for harried programmers: following the links and studying the information there gets you to the same place where your intuition tells you to go - that is, after converting the input number to factoradic (called factorial number system in the Wikipedia) its coefficients give you the desired permutation. Converting to and from factoradic can also be extremely useful for things like verifying the perfect uniformity of random_shuffle implementations in unit tests.