Solved

# Algorithm for Sequence Generator from given String

Posted on 2012-08-24
779 Views
Hello,
Please help me writing a C++, Java program to generate sequences from the given string. For example from string str("ABC") we need to generate all possible sequences like "A B C AB AC BC ABC")

Thanks for the help
0
Question by:sriram

LVL 84

Expert Comment

Do you need the sequences to be generated in that order?
Can we assume that the string will be no longer than, say, 32 characters?
0

LVL 37

Accepted Solution

A recursive solution would probably be the easiest.

``````string source = "ABC";
int length = source.length();
string current = "";

Generate(source, length, 0, 0,  current,);
``````

Then
``````//start is where in the source to start, position is where in current we are modifying
void Generate(const string &source, const int length, int start, int position, string &current)
{
if(start == length + 1)
printf("%s\n", current); //or however you do output, just output current
else
{
for(int i = start; i <= length; ++i) //Note: we allow i == length for the \0 to allow A, AB, etc
{
current[position] = source[i];
Generate(source, length, i+1, position+1, current);
}
}
}
``````
Note: This is C++ syntax and assumes order must be maintained. Also, I didn't test it. I mean, I'm not lazy. Any errors are left as an exercise to the student. Yeah.
0

Author Closing Comment

Thanks for the suggestions. I had to modify the program to make it work.
0

## Featured Post

### Suggested Solutions

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.