Hi experts,
I have a string like "abc",now I want to get the combination this string for number k,for example for "abc" and k=2
ab
ac
bc
I realy thought on it but I can't solve it recursivly,I know how to solve it unrecursivly but how to silve this recursively?
thanks.
abc
000
001
010
011*
100
101*
110*
111
The non-recursive slow approach is easy. The fast non-recursive approach takes a little more thinking.
There are a bunch of old threads on bit counters, which is basically what you're looking for.
http://onesearch.sun.com/search/onesearch/index.jsp?qp_name=null&qt=recursive+counter&subCat=siteforumid%3Ajava426&site=dev&dftab=siteforumid%3Ajava426&chooseCat=javaall&col=developer-forums
To pull k element from the last n elements of a string
either skip the first of the last n elements and pull k element from the last n-1 elements
or
include the first of the last n elements and pull k-1 elements from the last n-1 elements
.
There you go - recursive routine.
You need to build up a result string which you pass on down as you go along. You need to stop the recursion at the appropriate point, like when you are done building a result string, and you need to protect yourself from calling a recursive routine that can not be solved (like when k is too big)
Actual code takes about 6 lines.
Enjoy!
> The fast non-recursive approach takes a little more thinking.
Or some knowledge of HAKMEM. public static int foo(int a)
{
int c = a & -a;
int r = a + c;
a = (((r^a) >>> 2) / c) | r;
}
>either skip the first of the last n elements and pull k element from the last n-1 elements
or
>
include the first of the last n elements and pull k-1 elements from the last n-1 elements
well,I don't know how to write?
I write this one
[C#]
string results="";
private void comb(string s,int k,string answer)
{
//if?
string rem=s.Remove(0,1);//remove the first char
comb(s,k,answer);//?
}
but I don't know how to go on?
>
> [C#]
> string results="";
> private void comb(string s,int k,string answer)
> {
> //if?
> string rem=s.Remove(0,1);//remove the first char
> comb(s,k,answer);//?
> }
recursive solutions often have a public method and a private method.
The public method would look like:
public static void solve(String s, int k);
The private method would look like:
private static void solve(String s, int i, int k, StringBuffer sb);
initially, i == 0 and the sb is empty.
The "i" is the current index. What marlin said was:
either) add the character at index i to sb
or) don't add it
then, recurse calling solve(...,i+1,...)
you'll need to handle the base cases, which would be i == k and
i >= s.length(). Becareful about which order you handle the base
cases.
you should have something like:
handle base cases
add(c) to sb
recurse
remove c from sb
recurse
where c is the character at index location i.
hi rkipen,
thanks for the explanation
I can't get how to write it,I'm stuck in this problem,I have confused it with anoher problem
can you mention its code so I learn from it?
for example this code I have written would give me premunation(p(n,k)) not combination,but how to change it to combination,or even I can change so it could write prem with repeated locations(k^n) but I can't write its combination(c(n,k))
string result1="";
private void prem(string set,string answer,int n)
{
if(n<=0)
{
result+=answer+"\n";
return;
}
for(int i=0;i<set.Length;i++)
{
string remain=set.Remove(i,1);
prem(remain,answer+set[i],n-1);
}
}
thanks.>
public static void get(String s, int k) {
get(s, 0, k, new StringBuffer());
}
private static void get(String s, int i, int k, StringBuffer sb) {
// handle base case sb.length() == k
// handle base case for i
sb.append(s.charAt(i));
get(s, i+1, k, sb);
sb.deleteCharAt(sb.length() - 1);
get(s, i+1, k, sb);
}
I've intentionally removed the base case code (which is less than 3 lines).
Well if we're just gonna tell em, here's what I wrote.
// pull k chars from the last n of in into res and print res.
public static void pull(String in, int k, int n, String res){
if(k==0) System.out.println(res);
else{
char c = in.charAt(in.length() - n); // character that is first of the last n
pull(in, k-1, n-1, res+c);// consider all cases where you include c in your result
if(k<n) pull(in, k, n-1, res); // consider all cases where you DON'T include c in your result
}
}
public static void main(String args[]){
String in = "abcde";
pull(in,3,in.length(),"");
}
NOTE: we MUST guard the last recursive call. Why? Because if k==n then we MUST inclue all the the remaining chars. We do NOT have the option of skipping the character c. So this last case is only valid when there are plenty of characters left to choose from.
PS - make sure you sign my name when you hand this in. This code is copyrighted by me and the FBI will track you down, fine you $250,000 AND throw you in prison for 5 years for knowingly violating my copyright.
Enjoy!>