# Finding Kth Permutation Sequence

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);
// Getting 2 integer inputs with space

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")) {

}

return;
}

for (int i = 0; i < n; ++i) {

String newPrefix = prefix + set[i];

printAllKLengthRec(set, newPrefix, n, k - 1, prefixlist);
}

}

• Can you provide a few text examples of the input and output? – Zack Mar 8 '16 at 17:10
• 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 – arunprakashpj Mar 10 '16 at 2:10

• 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. – DarthGizka Apr 10 '16 at 5:48