# Produce the nth lexicographic permutation of a string consisting of letters H and V

I have tried many possible methods here but I am still not able to reduce the time complexity of below algorithm.

//This function returns the next lexicographical permutation of the StringBuilder s
static StringBuilder getKRankString(StringBuilder s)
{
char ch[] = (s.toString()).toCharArray();
int i = 0, j=0;
//This loop gets the highest i for which ch[i]<ch[i+1]
for(int k=0;k<s.length()-2;k++){
if(ch[s.length()-2-k]<ch[s.length()-1-k]){
i = s.length()-2-k;
break;
}

}
//System.out.println(i);
//This loop gets the highest j for which ch[j]>ch[i]
for(int k=s.length()-1;k>i;k--){
if(ch[k]>ch[i]){
j = k;
break;
}

}
//System.out.println(j);
//swap characters at i and j
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
//Append the original string till i to reversed string from i till end
StringBuilder swapped = new StringBuilder(new String(ch));
//System.out.println(swapped);
String sb1 = swapped.substring(0, i+1);
String sb2 = (new StringBuilder(swapped.substring(i+1, s.length())).reverse()).toString();
StringBuilder str = new StringBuilder(sb1+sb2);
return str;
}

static String[] gridLand(String[] inp) {
String[] outputArr = new String[inp.length];
for(int i=0;i<inp.length;i++){
//get the first line of input and get integer x and y
int x = Integer.valueOf(inp[i].split(" ")[0]);
int y = Integer.valueOf(inp[i].split(" ")[1]);
int k = Integer.valueOf(inp[i].split(" ")[2]);
StringBuilder sb = new StringBuilder();
//form the original string using x H's and y V's.
//This will be the first String of this order
for(int j = 0; j < x; j++)
sb = sb.append("H");
for(int j = 0; j < y; j++)
sb = sb.append("V");
//String s1 = sb.toString();
//run the below functoin K times to get Kth lexicographical string
for(int m = 0; m < k; m++)
sb = getKRankString(sb);
outputArr[i] = sb.toString();
}
return outputArr;

}⁠⁠⁠⁠


The basic layout of my problem is as follows: I have a string that is composed of only H's and V's. There can be not more than 10 H's and 10 V's possible. I need to find the Kth lexicographical order of such pattern. Also, inp[] array contains input is format:

2 2 3
4 5 4


which means that total H = 2, total V = 2 and I need to print 3rd lexicographical permutation of HHVV. Similarly for 4 5 4, I need to print 4th lexicographical permutation of HHHHVVVVV.

• For an algorithm that has a complexity linear to the length of the string, see the last part of this answer: stackoverflow.com/questions/34230266/… – m69 May 10 '17 at 4:46

Let P(n,m) be the number of permutations of n Hs and m Vs. For m>0 and n>0, P(n,m) = (n + m)!/(n! * m!).
Let's say you want the kth permutation of n Hs and m Vs:
If k <= P(n-1,m), then the answer is an H followed by the kth permutation of n-1 Hs and m Vs.
Otherwise the answer is a V followed by the (k-P(n-1,m))th permutation of n Hs and m-1 Vs.