Generating substrings of a string

[ashworcp]

I am trying to create programs to generate substrings of a string and also subsets of characters of a string.

For the substrings of the string "rum" there are seven: "r", "ru", "rum", "u", "um", "m", ""

For the subsets of the string "rum" there are eight: "r", "ru", "rum", "u", "um", "m", "rm", "".

So the only difference is "rm" in the second. I think I have created a program for the second one.

Here it is:

#include <iostream>

using namespace std;

void subsets(int i, int j) 
{
	static char input[] = "rum";
	static char output[sizeof input];

    output[j] = '\0';
	printf("%s\n", output);

    while(input[i] != '\0') {
        output[j] = input[i];
        subsets(i + 1, j + 1);
        do ++i;
        while(input[i] == input[i - 1]);
    }
}

int main() 
{
    cout << "The subsets of rum are: " << endl;
    subsets(0, 0);
    system("Pause");
    return 0;
}

I am confused on what to do for the first one because I feel it is so similar. Also, when I run my code, it skips a line for the first one. Does that mean it is the "" subset?

Thank you.

[Duthomhas]

The differences between subsets and substrings are two:
1. substrings may have repeat characters
2. substrings are ordered ("rm" != "mr")

For your your question about the skipped line, you can try the following for output and see for yourself:

    cout << "\"" << output << "\"\n";

Remember to use cout in your C++ programs.

Also, don't use system. See http://www.cplusplus.com/forum/articles/7312/ for more.

To get all substrings, you'll need to modify your algorithm to simply use a 'bubble' kind of pass through:

"rummy"
-->
'""
"r"
"ru"
"rum"
"rumm"
"rummy
""
"u"
"um"
"umm"
"ummy"
""
"m"
"mm"
"mmy"
""
"m"
"my"
""
"y"
""

You may want to consider how you want to handle all the empty substrings in your algorithm. My example lists them all.

Subsets are different. Try your algorithm with the string "rummier" to see what goes wrong. To calculate subsets, you need to guarantee against repeats at the very start... so either modify the original string or a copy of it to be a true set -- without any repeats. Then create subsets using binary addition:

"rummier"
-->
"rumie"
 00000 --> ""
 00001 --> "e"
 00010 --> "i"
 00011 --> "ie"
 00100 --> "m"
 00101 --> "me"
 00110 --> "mi"
 00111 --> "mie"
 01000 --> "u"
 01001 --> "ue"
 01010 --> "ui"
 01011 --> "uie"
 01100 --> "um"
 ...

Also, two suggestions:
1. Use std::strings
2. Don't use static variables in your function. Pass stuff in via argument lists. This alows you to do things like ask the user to enter any string and then calculate the substrings and subsets.

Hope this helps.

Typing with one hand is frustratingly slow... (with my infant daughter in the other hand)