Saturday, 31 March 2012

Find the kth permutation of the string

Print the kth permutation of the given string.
e.g.
5th permutation of "abc" is "cab", because its comes on 5th position in the ordered list of its permutations as shown below:
abc
acb
bac
bca
cab
cba

My Code:

import java.util.Arrays;




public class Main {


    public static String getStr(StringBuffer perm, int k){ // perm is not the original string it has the non repeating string chars
        String r = "";
        //System.out.println(perm);
        
        if(k<1)
            return perm.toString();
        int n = 0, t= 1, ctr = 1, k_n = 0;;
        for(int i=1;;i++){
            t *= i;
            if(t>k){
                break;
            }
            ctr = i;
            n = t;
        }
        k_n = k/n;
        // take care of this n, i.e. reverse upto position i
        int pos = perm.length()-ctr;
        if(pos<0){
            //System.out.println("ERROR !!");
        }
        //mov e bfor b
        int e = pos-1+k_n;
        int b = pos-1;
        if(b<0){
            return getStr(perm, k-(n*k_n));
        }
        String tmp = perm.substring(0,b)+ perm.charAt(e) + perm.substring(b,e) ;
        if(e+1<perm.length()){
            tmp += perm.substring(e+1);
        }
        
        /*System.out.println(perm);
        System.out.println("\n ** nxt level ***\n");*/
        return getStr(new StringBuffer(tmp), k-(n*k_n));
        //return r;
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
      System.out.println(getStr(new StringBuffer("abcd"),5));
    }
}

No comments:

Post a Comment