4
\$\begingroup\$

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

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.

//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;

}⁠⁠⁠⁠
\$\endgroup\$
1
  • \$\begingroup\$ ch, i, j, s, str, sb1, sb2, x, y, inp, m -- are not real variable names. Do you think anybody can quickly understand what each of these means? Noone should ever use names like that. You're asking for performance improvements, but readability and correctness already suffer. \$\endgroup\$ Commented May 11, 2017 at 1:51

2 Answers 2

5
\$\begingroup\$

Encoding

I hope I understood the problem correctly :)

When observing the problem, I found you can replace the H and V with 0 and 1. The lexicographical permutations then become binary numbers. There are only 10 V's and 10 H's, so the final number will be below 2^20 so fits even in an int.

   HHHVV -> 00011
   VVHHH -> 11000
   etc.

Start out by setting the starting int to (1 << Vs) -1 and use the next-bit permutation logic from here

Then, if you found the nth permutation, transform it back to a String

Time complexity

As calculation the next bit permutation is simply a constant time calculation, finding the nth permutation takes O(n) time.

Proposed solution

public class Permutations
{
    //treat H as 0, V as 1.
    private static String getLongAsHVString( long size, long l )
    {
        String s = Long.toBinaryString( l ).chars().mapToObj( Permutations::getStr ).collect( Collectors.joining() );

        //Prepend the 'missing' zeroes as 'H' s
        while ( s.length() < size )
        {
            s = "H" + s;
        }
        return s;
    }

    private static String getStr( int c )
    {
        return ( c == '0' ) ? "H" : "V";
    }

    private static long getNthLexoPerm( int hCount, int vCount, int n )
    {
        long current = ( 1 << vCount ) - 1;

        for ( int i = 0; i < n; i++ )
        {
            current = nextPerm( current );
        }
        return current;
    }

    private static String getNthLexoPermAsString( int hCount, int vCount, int n )
    {
        return getLongAsHVString( hCount + vCount, getNthLexoPerm( hCount, vCount, n ) );

    }

    public static long nextPerm( long v )
    {
        long t = ( v | ( v - 1 ) ) + 1;
        return t | ( ( ( ( t & -t ) / ( v & -v ) ) >> 1 ) - 1 );

    }

    public static void main( String[] args )
    {

        System.out.println( getNthLexoPermAsString( 2, 2, 3 ) );
        System.out.println( getNthLexoPermAsString( 4, 5, 4 ) );
    }

}
\$\endgroup\$
2
  • \$\begingroup\$ Correct approach, but bit twiddling doesn't work for long strings. +1 anyway. \$\endgroup\$
    – vnp
    Commented May 10, 2017 at 17:04
  • \$\begingroup\$ great solution! \$\endgroup\$
    – CodeHunter
    Commented May 10, 2017 at 17:26
2
\$\begingroup\$
static StringBuilder getKRankString(StringBuilder s)

Is this supposed to be a fluent method which modifies s and returns it? That would be the obvious reason for having this signature, but it isn't what the method actually does. Better javadoc required.


    char ch[] = (s.toString()).toCharArray();

Why? This does a lot of copying for no obvious benefit.


    //This loop gets the highest i for which ch[i]<ch[i+1]
    for(int k=0;k<s.length()-2;k++){

If you want the highest one, why start from the other end?


        if(ch[s.length()-2-k]<ch[s.length()-1-k]){
            i = s.length()-2-k;

Maybe worth pulling out s.length() into a variable for readability?


    //System.out.println(i);

I strongly encourage removing debug code before code review.


    //Append the original string till i to reversed string from i till end
    StringBuilder swapped = new StringBuilder(new String(ch));

If you're not going to modify the original in place, you might as well at least create the one you are going to modify directly from the original one, to reduce the number of times you copy the entire string. This line here copies it twice, once in the String constructor and once in the StringBuilder constructor!


    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);

By now I'm starting to wonder whether you realise that the point of StringBuilder is that it's mutable.

Rewriting this method to use StringBuilder as a mutable string (or to throw it away entirely and use char[] if you find that conceptually simpler) wouldn't change the asymptotic performance, but I think you've got a potential speedup of about five times.


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]);

The code would be better structured if the input parsing and the processing logic were separated.


            sb = sb.append("H");

The reason that StringBuilder.append returns itself is so that you can chain calls: sb.append(foo).append(bar).append(baz). If you just want to mutate the contents it's not necessary to do anything with the return value.


    //run the below functoin K times to get Kth lexicographical string
        for(int m = 0; m < k; m++)
            sb = getKRankString(sb);

If you want to improve the asymptotic performance, this is the problem. You need to apply combinatorics, and then you should be able to make the performance almost independent of k.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.