about java recursion to create combination of string

Question

The question was asking me to return set containing all the possible combination of strings made up of "cc" and "ddd" for given length n.

so for example if the length given was 5 then set would include "ccddd" and "dddcc". and length 6 would return set containing "cccccc","dddddd"
and length 7 would return set contating "ccdddcc","dddcccc","ccccddd" and length 12 will return 12 different combination and so on

However, set returned is empty. Can you please help?

"Please understand extremeply poor coding style"

public static Set<String> set = new HashSet<String>();

public static Set<String> generateset(int n) {


    String s = strings(n,n,"");


    return set; // change this
}

public static String strings(int n,int size, String s){


    if(n == 3){
        s = s + ("cc");
        return "";}
    if(n == 2){
        s = s + ("ddd");
        return "";}
    if(s.length() == size)
        set.add(s);

    return strings(n-3,size,s) + strings(n-2,size,s); 
}

check this(http://stackoverflow.com/questions/18271094/java-for-creating-all-possible-combination-of-words) — bananas, Oct 15 '16 at 04:53

ajb · Accepted Answer · 2016-10-15T15:53:55.483

I think you'll need to rethink your approach. This is not an easy problem, so if you're extremely new to Java (and not extremely familiar with other programming languages), you may want to try some easier problems involving sets, lists, or other collections, before you tackle something like this.

Assuming you want to try it anyway: recursive problems like this require very clear thinking about how you want to accomplish the task. I think you have a general idea, but it needs to be much clearer. Here's how I would approach the problem:

(1) You want a method that returns a list (or set) of strings of length N. Your recursive method returns a single String, and as far as I can tell, you don't have a clear definition of what the resulting string is. (Clear definitions are very important in programming, but probably even more so when solving a complex recursive problem.)

(2) The strings will either begin with "cc" or "ddd". Thus, to form your resulting list, you need to:

(2a) Find all strings of length N-2. This is where you need a recursive call to get all strings of that length. Go through all strings in that list, and add "cc" to the front of each string.

(2b) Similarly, find all strings of length N-3 with a recursive call; go through all the strings in that list, and add "ddd" to the front.

(2c) The resulting list will be all the strings from steps (2a) and (2b).

(3) You need base cases. If N is 0 or 1, the resulting list will be empty. If N==2, it will have just one string, "cc"; if N==3, it will have just one string, "ddd".

You can use a Set instead of a list if you want, since the order won't matter.

Note that it's a bad idea to use a global list or set to hold the results. When a method is calling itself recursively, and every invocation of the method touches the same list or set, you will go insane trying to get everything to work. It's much easier if you let each recursive invocation hold its own local list with the results. Edit: This needs to be clarified. Using a global (i.e. instance field that is shared by all recursive invocations) collection to hold the final results is OK. But the approach I've outlined above involves a lot of intermediate results--i.e. if you want to find all strings whose length is 8, you will also be finding strings whose length is 6, 5, 4, ...; using a global to hold all of those would be painful.

Thank you! recursion is still difficult concept for me to understand. — , Oct 15 '16 at 05:32
I get the idea of what you are trying to say but I guess my java is simply not good enough to implement it. I will probably have to spend reasonable amount of time to come up with methods you described. Thank you so much again for the kind help. — , Oct 15 '16 at 05:40

score 0 · Answer 2 · answered Oct 15 '16 at 05:29

0

The answer to why set is returned empty is simply follow the logic. Say you execute generateset(5); which will execute strings(5,5,"");:

First iteration strings(5,5,""); : (s.length() == size) is false hence nothing added to set

Second iteration strings(2,5,""); : (n == 2) is true, hence nothing added to set

Third iteration strings(3,5,""); : (n == 3) is true, hence nothing added to set

So set remains un changed.

answered Oct 15 '16 at 05:29

c0der

18,467
6
33
65

Thank you so much! – Oct 15 '16 at 05:31

about java recursion to create combination of string

2 Answers2