Simple recursion problem. Need help.

[Anakin]

I have this simple recursion problem that i need to solve. It starts
with the following string:

String element = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

I need to generate and print on screen all combinations of uppercase
letters, given a group of starting letters. In other words, if I say
that I want all combinations of the first three letters of the alphabet
– ABC – then I need to generate ABC, AB, AC, BC, A, B, C. The order of
the letters is not actually important. So I need to write a recursive
implementation of a method that will generate all such strings for a
given number of letters. In other words, the user would give me the
letter count and I provide the list of combinations. (for testing
purposes, I could print this on screen). Also, I'm not allowed to use
any loops for my recursion.

I tried to do this recursion part, but this is driving me crazy. I only
found how to do this using loops. There must be an easier way without loops.

please help. thanks.

Paul M.

public static void recursive(String S, Set dataSet){
int len = S.length();
String temp = "";

if (len == 1) {
System.out.println(S);
}
else {
System.out.println(S);
for (int j=len-1; j>=0; j--) {
for (int k=0; k<len; k++) {
if (k != j) temp += S.charAt(k);
}
System.out.println(S);
recursive(temp, dataSet);
temp = "";
}
}
}

 

[Thomas Weidenfeller]

I tried to do this recursion part, but this is driving me crazy.

You know, we don't do homework here. We don't want to deprive people of
their (paid for) learning experience.

You might want to get a good start by working through

http://home.earthlink.net/~patricia_shanahan/beginner.html

and reading your textbook and course notes again.

/Thomas

 

[Anakin]

Nice. real nice. hmm let's see where should i start.. I *did* read my
textbook as well as other books. I *did* go through my course notes.
*all* of them. I *did* use google and other search engines to find out
anything even a HINT of how i'm supposed to solve this problem. And yes,
before you ask, I *did* approach my own teacher about this. He refused
to help me and any other students with this problem (yes, professors
like that do actually exist) saying any hints he would give would be
like giving the solution away. The only thing to do, he says, is to
spend some time and think about it. I spent *days* thinking about this
before I actually wrote post asking for help on this now.

btw, this isn't a typical java problem. if it was, i wouldn't be posting
here as i am a reasonably experienced programmer. no, this is a question
about recursion. do you even know what a recursion is? you can't just
re-direct someone to a java beginners website and ask him to read from
there. This problem requires mathematical thinking. something that i'm
trying to develop along with my coding practices. Since programmers are
supposed to be familiar with recursions and the fact that i'm writing my
entire code in java, I was assuming this was the right place to ask for
help.

Also, this is only a *small* part of my program. I am NOT asking anyone
here to do my homework, as Thomas seems to be implying. Any help, even a
hint could be helpful to me. So Thomas, please take your dumb remark
elsewhere. This will be my last reply to you unless you have anything
actually *constructive* about my problem to add.

Paul M.

 

[Jussi Piitulainen]

to do, he says, is to spend some time and think about it. I spent
*days* thinking about this before I actually wrote post asking for
help on this now.

Suppose you can compute all combinations of "BC". They are just the
combinations of "ABC" that do not contain A. For the combinations of
"ABC" that do contain A, add A to each. Do not forget the empty
combination.

 

[SPG]

Nice. real nice. hmm let's see where should i start.. I *did* read my
textbook as well as other books. I *did* go through my course notes. *all*
of them. I *did* use google and other search engines to find out anything
even a HINT of how i'm supposed to solve this problem. And yes, before you
ask, I *did* approach my own teacher about this. He refused to help me and
any other students with this problem (yes, professors like that do
actually exist) saying any hints he would give would be like giving the
solution away. The only thing to do, he says, is to spend some time and
think about it. I spent *days* thinking about this before I actually wrote
post asking for help on this now.

btw, this isn't a typical java problem. if it was, i wouldn't be posting
here as i am a reasonably experienced programmer. no, this is a question
about recursion. do you even know what a recursion is? you can't just
re-direct someone to a java beginners website and ask him to read from
there. This problem requires mathematical thinking. something that i'm
trying to develop along with my coding practices. Since programmers are
supposed to be familiar with recursions and the fact that i'm writing my
entire code in java, I was assuming this was the right place to ask for
help.

Also, this is only a *small* part of my program. I am NOT asking anyone
here to do my homework, as Thomas seems to be implying. Any help, even a
hint could be helpful to me. So Thomas, please take your dumb remark
elsewhere. This will be my last reply to you unless you have anything
actually *constructive* about my problem to add.

Paul M.

Young Vader... Hold on to your dummy for a while...
Have you tried looking at the regex functionality for java?

I don't want to give the answer away to you, but have a look at Pattern and
Match objects, and also how they are combined with the String object..

I think this may be the pointer you needed....

HTH - Steve

 

[Chris Uppal]

Have you tried looking at the regex functionality for java?

What ?!?

-- chris

 

[Chris Uppal]

[..] if I say
that I want all combinations of the first three letters of the alphabet
– ABC – then I need to generate ABC, AB, AC, BC, A, B, C.

Don't forget the empty case where there are no letters to print -- you can't
solve this problem without remembering that. So the solution in this case
is (re-ordered for reasons that should become evident later).

"ABC" "AC" "BC" "C" "AB" "A" "B" and ""

If the problem were slightly smaller, printing out the combinations of the
first two letters of the alphabet, then the solution would be:
"AB" "A" "B" and ""

Can you see the connection between the solution with 'C' and without it ? If
so then you should be able to see how to solve the 3-letter problem by
recursively solving the smaller 2-letter problem.

HTH (but not /too/ much ;-)

-- chris

 

[Chris Uppal]

the user would give me the
letter count and I provide the list of combinations. (for testing
purposes, I could print this on screen).

Oh, yes. I forgot to mention: you'll probably find it easier to solve this if
you /don't/ print solutions out on the screen until you've found all of them.
I.e. write a (recursive) method that returns some sort of collection of
Strings.

It is possible write a recursive solution that doesn't use collections of
strings, but instead prints stuff out as it finds it, but you will probably
find that significantly harder -- at least until after you've found the simpler
solution using collections.

-- chris

 

[googmeister]

I have this simple recursion problem that i need to solve. It starts
with the following string:

String element = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

Since the advice so far as been remarkably unhelpful, I'll give it a
shot.
First, here's a slightly simpler version of your program with only
one loop. [Presumably N is small so using string concatenation won't
be a big deal.]

public static void generate(String prefix, String elements) {
System.out.println(prefix);
for (int i = 0; i < elements.length(); i++)
generate(prefix + elements.charAt(i), elements.substring(i +
1));
}

generate(elements.substring(0, N);


Now, to remove recursion entirely, try implementing the loop part using
a *second* tail-recursive function. So you'll end up with a total of
two
recursive functions, but no loops.

 

[googmeister]

An alternate approach is to use bit-whacking. Note that there
are 2^N subsets of size N. You can enumerate them by counting
from 0 to 2^N-1 by 1 and looking at the bit-representation. Again,
if you use tail-recursion instead of a loop, you can eliminate
recursion. (Of course, the only purpose of recursion here
is to satisfy the requirements of the assignment.)

 

[Patricia Shanahan]

Nice. real nice. hmm let's see where should i start.. I
*did* read my textbook as well as other books. I *did* go
through my course notes. *all* of them. I *did* use
google and other search engines to find out anything even
a HINT of how i'm supposed to solve this problem. And
yes, before you ask, I *did* approach my own teacher
about this. He refused to help me and any other students
with this problem (yes, professors like that do actually
exist) saying any hints he would give would be like
giving the solution away. The only thing to do, he says,
is to spend some time and think about it. I spent *days*
thinking about this before I actually wrote post asking
for help on this now.

btw, this isn't a typical java problem. if it was, i
wouldn't be posting here as i am a reasonably experienced
programmer. no, this is a question about recursion. do
you even know what a recursion is? you can't just
re-direct someone to a java beginners website and ask him
to read from there. This problem requires mathematical
thinking. something that i'm trying to develop along with
my coding practices. Since programmers are supposed to be
familiar with recursions and the fact that i'm writing my
entire code in java, I was assuming this was the right
place to ask for help.

Also, this is only a *small* part of my program. I am NOT
asking anyone here to do my homework, as Thomas seems to
be implying. Any help, even a hint could be helpful to
me. So Thomas, please take your dumb remark elsewhere.
This will be my last reply to you unless you have
anything actually *constructive* about my problem to add.


Paul M.

It is part of your homework, and it seems your professor
feels strongly that you need to think it through for yourself.

http://www.nist.gov/dads/HTML/recursion.html has an
explanation of recursion that I like, and a graduated series
of exercises to build up the right way of thinking about it.
None of those exercises is your homework problem, so you can
ask for help with them without any ethics problems.

Patricia

 

[Kevin]

I have this simple recursion problem that i need to solve. It starts
with the following string:

String element = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

I need to generate and print on screen all combinations of uppercase
letters, given a group of starting letters. In other words, if I say
that I want all combinations of the first three letters of the alphabet
ABC then I need to generate ABC, AB, AC, BC, A, B, C.

This is called a permutation.

The order of the letters is not actually important.

Specifically, this is called an unordered permutation.

So I need to write a recursive
implementation of a method that will generate all such strings for a
given number of letters. In other words, the user would give me the
letter count and I provide the list of combinations. (for testing
purposes, I could print this on screen). Also, I'm not allowed to use
any loops for my recursion.

I tried to do this recursion part, but this is driving me crazy. I only
found how to do this using loops. There must be an easier way without loops.

please help. thanks.

Paul M.

public static void recursive(String S, Set dataSet){
int len = S.length();
String temp = "";

if (len == 1) {
System.out.println(S);
}
else {
System.out.println(S);
for (int j=len-1; j>=0; j--) {
for (int k=0; k<len; k++) {
if (k != j) temp += S.charAt(k);
}
System.out.println(S);
recursive(temp, dataSet);
temp = "";
}
}
}

The code above is called PART 1 of a two part assignment. You got the
iteration part, assuming the above code earned you a decent grade. I
won't give you the answer to PART 2. But I will suggest you bone up on
your google skills.

I found 50,000 hits on permutation+recursion. I'm sure at least one
or two of those include actual code. But I'll add a very helpful
warning. The quickest way to tackle this problem is to understand
the algorithm first then implement it on your own. Jumping on someone
else's code is the worst approach you can take, both for the sake of
time and your own education.

 

[wolfgang zeidler]

I have this simple recursion problem that i need to solve. It starts
with the following string:

String element = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

I need to generate and print on screen all combinations of uppercase
letters, given a group of starting letters. In other words, if I say
that I want all combinations of the first three letters of the alphabet
– ABC – then I need to generate ABC, AB, AC, BC, A, B, C. The order of
the letters is not actually important. So I need to write a recursive
implementation of a method that will generate all such strings for a
given number of letters. In other words, the user would give me the
letter count and I provide the list of combinations. (for testing
purposes, I could print this on screen). Also, I'm not allowed to use
any loops for my recursion.

I tried to do this recursion part, but this is driving me crazy. I only
found how to do this using loops. There must be an easier way without
loops.

please help. thanks.

Paul M.

Hello,

the 8 results for the "ABC problem" are:
C
A AC
B BC
AB ABC

Notify:
left part above are also the results for the "AB problem",
right part = left part + suffix "C"

Here is a short java*script* solution for the "ABC problem":
<script type="text/javascript"><!--
function m3 ( s ) { m2 ( s ); m2 ( 'C' + s ); }
function m2 ( s ) { m1 ( s ); m1 ( 'B' + s ); }
function m1 ( s ) { m0 ( s ); m0 ( 'A' + s ); }
function m0 ( s ) { document.write ( s + '|<br>' ) }
m3 ( '' )
</script>

toDo:
1) you may replace call "m3 ( '' )" with "m2 ( '' )" to get the "AB
solution"
2) your job|exercise: translate this javascript to java
3) try method "m3 ( '' )" to get the "ABC solution",
try method "m2 ( '' )" to get the "AB solution"
4) your job|exercise: replace methods "m0 (s)", ..., "m3 (s)"
with *one* method "mRec ( s , r )"
5) try method "mRec ( '' , 2 )" to get the "AB solution",
try method "mRec ( '' , 3 )" to get the "ABC solution",
try method "mRec ( '' , 4 )" to get the "ABCD solution",
*don't* try method "mRec ( '' , 26 )",
you would get more than 67 millions lines of output.

Regards, wz.

 

[googmeister]

ABC then I need to generate ABC, AB, AC, BC, A, B, C.

This is called a permutation.

Specifically, this is called an unordered permutation.

It's more common to call this a combination.

 

[Thomas G. Marshall]

Chris Uppal coughed up:

What ?!?

-- chris

LOL. What he said. {still chuckling...}