Recursively spell out a word

I was given this:

Write a recursive program that, given a string with no spaces in it, breaks it into every possible segmentation of the string into "words". That is, print out every possible version of the string with spaces inserted in it. The order in which the segmented strings are given does not matter, but all possible segmentations must be given, with no repeats.

and at am a complete loss on how to even start, if so开发者_JS百科meone could help.

The output is supposed to look like this:

 Enter a string: ABCD

 ABCD
 A BCD
 A B CD
 A B C D
 A BC D
 AB CD
 AB C D
 ABC D

I will give you hints to help:

Think about how to solve this issue recursively. Basically, this could be solved with a variation of "divide and conquer". For a given string of length n, there are n-1 places where you can insert separator spaces.

Thus if you have a string of length 2, you have one place to insert a separator, and two variations: either you insert the separator, or not.

If you have a string of length 3, you have 2 choices in 2 places. Thus the function can create a string with the space inserted in the first place, and recursively call itself with the unprocessed tail of the string to produce all variations for that substring. Then create another prefix string where there is no space inserted in the first place, and again call itself with the rest of the string.

For each recursive call, it needs to pass itself the already generated prefix of the string, and the remaining unprocessed tail of the string.

There's a pattern to the output you've been given (as in, in the order in which those outputs have been produced). Consider what outputs 2-5 have in common:

A BCD
A B CD
A B C D
A BC D

So, it looks like your function is going to print its input (ABCD), then it's going to take the first letter as a prefix (A), and recursively find all combinations of its remaining letters (BCD). This would hint that the actual definition for the function takes two parameters - a prefix that has already been expanded, and a set of remaining letters to enumerate the combinations for.

Having done that with one letter, we then move another letter across into this prefix (AB), and again recursively find all combinations for the remaining letters (CD), to produce the next set of outputs:

AB CD
AB C D

Thanks for being honest about this being homework. A trick for writing a recursive function Foo(n) is to assume that Foo(n-1) already works as it should. In this case, you are tasked with writing a function GenerateSpaceVariationsOfString(string s), which takes a string s as parameter and should return an array containing all possible variations of the string. (It will be easier to make a recursive function what returns its result rather than one that prints its results - then, you can just print the array you get from the function.) Let's say that s is of length n. Now, assume that you have a function that can take s minus its first letter and return an array of all possible space variations of that substring - in other words, assume that GenerateSpaceVariationsOfString(s.substring(1)) would give {"BCD", "BCD", "BC D", "BC D", ...} if s is ABCD. How could you use this to write GenerateSpaceVariationsOfString?

(In recursion, you also need a base case, so what should GenerateSpaceVariationsOfString(s) return if the length of s is 0 or 1?)

A simple recursive algorithm can be implemented if you realize that the segmentation of a string s is equal to a set containing s itself, and a set union of each substring X of s with the segmentation of s\X. Also, since you will always have n-1 possible substrings, and you can either segment or not segment in each of these points, you will always end up with 2^(n-1) segments.

It is more simple to understand with an example for the segmentation of the string ABC:

1. {'ABC'} // 'ABC' itself
2. {'A', 'B, 'C'} // substring 'A' union 1st segmentation of 'BC' = {'B, 'C'}
3. {'A', 'BC'} // substring 'A' union 2nd segmentation of 'BC' = {'BC'}
4. {'AB', 'C'} // substring 'AB' union 1st and only segmentation of 'C' = {'C'}
5. Union of 1, 2, 3, and 4, yield all segmentations of the string ABC.

This translates almost directly to the following implementation:

public static Set<Set<String>> segment(String s) {
    // `s` itself.
    Set<Set<String>> result = new LinkedHashSet<Set<String>>();
    Set<String> root = new LinkedHashSet<String>();
    root.add(s);
    result.add(root);   

    // set union of each substring `X` (prefix) of `s` with `s\X` (rest).
    for (int i = 1; i < s.length(); i++) {   
        String prefix = s.substring(0, i);
        String rest = s.substring(i);
        for (Set<String> segments : segment(rest)) {
            Set<String> segment = new LinkedHashSet<String>();
            segment.add(prefix);
            segment.addAll(segments);
            result.add(segment);
        }
    }
    return result;
}

Sample outputs:

System.out.println(segment("ABC"));
// [[ABC], [AB, C], [A, B, C], [BC, A]]
System.out.println(segment("ABCD"));
// [[D, AB, C], [BCD, A], [D, ABC], [D, A, B, C], [AB, CD], [ABCD], [D, BC, A], [A, B, CD]]

Think of the joint between two letters as one bit. If the bit is 1, then you insert a space there, if it's 0, you don't. So if the string length is n, you create a bit sequence that's n-1 in length. Then you treat the bit sequence as an unsigned integer, and loop through all the possible values: 000, 001, 010 etc.

Of course, this isn't recursive, so you won't get credit for it.