patternjavaMinor

Find lexicographical permutations

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

permutationslexicographicalfind

Problem

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]
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(in

Solution

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

    }

    public static void main( String[] args )
    {

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

}

Code Snippets

HHHVV -> 00011
   VVHHH -> 11000
   etc.

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

}

Context

StackExchange Code Review Q#162952, answer score: 5

Revisions (0)

No revisions yet.