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