Algorithm for Sequence Generator from given String

Posted on 2012-08-24
Last Modified: 2012-09-04
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
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?
    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,);

    Open in new window

    //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
        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);

    Open in new window

    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.

    Author Closing Comment

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

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Highfive + Dolby Voice = No More Audio Complaints!

    Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

    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…
    Article by: Nadia
    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.

    779 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    12 Experts available now in Live!

    Get 1:1 Help Now