CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 24
  1. #1
    Join Date
    Apr 2003
    Posts
    2

    All Combinations of the alphabet

    OK, so I'm trying to write some C++ code that will generate all combinations, of any size of the letters of the alphabet. so...

    A
    AB
    AC
    AD
    AE

    etc etc etc. the code I have now get a good amount of the combinations, but only keeps the combinations in oreder. ex: it gets ABE but not ACE, it gets CDF, but not CEF. here's what I have so far:

    void main()
    {
    const int NUMITEMS = 26;
    char items[100] = "";
    for(int w=0; w< NUMITEMS; w++)
    {
    items[w] = (char)(start+w);
    }
    items[NUMITEMS] = '\0';
    int num =0;
    char temp[26];
    for(int startPlace=0; startPlace<NUMITEMS; startPlace++)
    {
    for(int length=1; length<NUMITEMS-(startPlace-1); length++)
    {
    for(int last=startPlace+length-1; last<NUMITEMS; last++)
    {
    if(length == 1)
    {
    temp[0] = items[startPlace];
    temp[1] = '\0';
    last = NUMITEMS+1;
    }
    else
    {

    int i=0;
    while(i<length-1)
    {
    temp[i] = items[startPlace+i];
    i++;
    }
    temp[length-1] = items[last];
    temp[length] = '\0';
    }
    //Code to calculate the best answer.


    cout << temp<< "\n";
    }
    }
    }
    }

    can anyone tweak my solution to help me get all of them or give come up with some code that will get them all?

    PS: I'm looking for combinations, not permitations. Order Doesn't matter.

    Thanks!

    Jeff
    Attached Files Attached Files

  2. #2
    Join Date
    Apr 2003
    Location
    Morelia, Mexico
    Posts
    40
    Did a quick recursive implementation, it outputs to the screen, store the desired length of the string in "longitud".

    I didn't add any sort of validation, i recommend you to add it.
    Attached Files Attached Files
    int i;main(){for(;i["]<i;++i){--i;}"];read('-'-'-',i+++"hell\
    o, world!\n",'/'/'/'));}read(j,i,p){write(j/p+p,i---j,i/i);}

  3. #3
    Join Date
    Apr 1999
    Posts
    27,449
    Here is a general implementation. It uses a templatized class, therefore it will get the combinations of any type of variable, not just characters.

    The program takes advantage of the next_permutation algorithm and uses a set of bits to determine what to output. The way it works is that you call the NextCombination() function until there are no more combinations left.

    I attached the full code, but I'll go over the main() function briefly:
    Code:
    int main()
    {
        std::string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        vector<char> elements(alpha.begin(), alpha.end());
        vector<char> results(alpha.length() + 1, 0);
    All this does is initialize my vectors that will be used. The "elements" vector is a vector of all of the items I want to take the combination of. The "results" will hold the results of each time I get a combination. Note that the template allows combinations of char type. If I wanted to get the combination of integers, I change the type to <int> (this is done by template magic).
    Code:
        int nItems = 2;
        CombinationGenerator<char> CG(elements, nItems);
    This declares an instance of a CombinationGenerator class that will generate combinations. The first argument is the vector of all the items, and the second argument is the number I want to choose. For your case, it would be 2 characters. Also note that this is a templatized class that is based on "char", since the items are char items.
    Code:
        int nTries = 0;
        while (CG.NextCombination(results))
        {
            // Output our results
            int nSize = results.size();
            for ( int j = 0; j < nSize; j++ )
                    cout << results[j] << " ";
            cout << endl;
            nTries++;
        }
        cout << "Number of combinations is " << nTries << endl;
    }
    I just call CG.NextCombination() in a loop. The arguments to NextCombination is the vector that will be used to store the next combination.

    You should compile and run the program through a debugger. You will see that it will choose 2 letters out of 26 and output all of them. Again, this is a generalized function that will work with any type of data, not just chars. For example you can have a vector of complex structures (call it YourType), and if you want to take the combination of them, do the following:

    CombinationGenerator<YourType>(vector_of_YourType, number to_choose);

    And call NextCombination() as I did in a loop.

    Regards,

    Paul McKenzie
    Attached Files Attached Files
    Last edited by Paul McKenzie; April 21st, 2003 at 04:42 AM.

  4. #4
    Join Date
    Sep 2002
    Location
    Singapore
    Posts
    673
    jrlambs :If you intend to get all combinations as you stated, there are total of 66 million different combinations.

    Here's an article written by me. Hope it helps.
    Last edited by CBasicNet; April 21st, 2003 at 07:25 AM.

  5. #5
    Join Date
    Dec 2001
    Location
    Ontario, Canada
    Posts
    2,236
    std::string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    vector<char> elements(alpha.begin(), alpha.end());
    Paul this is unlike you; Using the std qualifier for string but not vector

  6. #6
    Join Date
    Apr 1999
    Posts
    27,449
    Originally posted by mwilliamson


    Paul this is unlike you; Using the std qualifier for string but not vector
    Yeah, but I had the "using namespace std" to bail me out

    Regards,

    Paul McKenzie

  7. #7
    Join Date
    Apr 2003
    Posts
    2
    Ok, so these are giving me all permutations, I need all combinations... I don't cae about the difference between ABC and ACB. only about the difference between ABC and ABE and ABF etc etc etc.

    thanks for all your hlp so far!

    Jeff

  8. #8
    Join Date
    Apr 1999
    Posts
    27,449
    Originally posted by jrlambs
    Ok, so these are giving me all permutations,
    Huh??

    My code does give combinations. Why do you think the name of the function that I wrote is NextCombination? Change the number of items to choose to 3, run it and you'll see the results.

    Regards,

    Paul McKenzie

  9. #9
    Join Date
    Apr 1999
    Posts
    27,449
    I changed the string to "ABCDEF" and the number of items to choose is 3. The number of combinations is 6! / (3! * 3!) = 20.

    Here is the output from the program I posted:
    -----------------------------------------------------------
    D E F
    C E F
    C D F
    C D E
    B E F
    B D F
    B D E
    B C F
    B C E
    B C D
    A E F
    A D F
    A D E
    A C F
    A C E
    A C D
    A B F
    A B E
    A B D
    A B C
    Number of combinations is 20
    ---------------------------------------------------

    Where do you see the permutations?

    Regards,

    Paul McKenzie

  10. #10
    Join Date
    Apr 2003
    Location
    Morelia, Mexico
    Posts
    40
    He probably saw it on mine, not yours.
    int i;main(){for(;i["]<i;++i){--i;}"];read('-'-'-',i+++"hell\
    o, world!\n",'/'/'/'));}read(j,i,p){write(j/p+p,i---j,i/i);}

  11. #11
    Join Date
    Jan 2001
    Posts
    253
    Hi Paul McKenzie,

    I would just like to say that I found your sample for outputting combinations very elegant. I had not thought of using next_permutation on a vector of bools to provide combinations.

    I was wondering if you came up with this yourself, or if it came from some book (and if so, what book did you find it in).

    Best regards,
    John

  12. #12
    Join Date
    Apr 1999
    Posts
    27,449
    Originally posted by jwbarton
    Hi Paul McKenzie,

    I would just like to say that I found your sample for outputting combinations very elegant. I had not thought of using next_permutation on a vector of bools to provide combinations.

    I was wondering if you came up with this yourself, or if it came from some book (and if so, what book did you find it in).

    Best regards,
    John
    Actually, I learned this in my second Comp Sci. course I took in college. The original code was written in PL/I and there was no official name for doing combinations this way. Just something I also thought was elegant and unique.

    For those who want to understand what is really going on, to get the combination of N things taken R at a time, my code creates an array of N bools. I then set the right-most "R" bools to "true" and the other N-R bools are set to "false".

    Assume the array of bools is B[] and the array of original items is O[]. For each element "i" of the B[] array, if the value in B[ i ] is "true", you output the corresponding O[ i ] element. Once this loop is done, you have outputted one combination. The next step is now to take the array of bools and get the next permutation of bools. This will move the "true" values around in the bool array. You repeat the loop again, checking it against the O[i] array. Again, you will output another combination.

    Example:
    Combination of 6 things taken 3 at a time.

    The O[] array consists of "ABCDEF" (the 6 items)
    The B[] array consists of 000111 (the '1' is true, '0' is false)

    Compare B[] for 1's:
    The first combination would be ---DEF

    Permute the bools:
    001101
    The next combination would be ---CD-F

    Permute the bools:
    001110
    The next combination would be --CDE-

    etc.

    So basically, if you have the code to output a permutation, you also have the code to output a combination. For C++, the next_permutation solves the permutation problem. Then it's all a piece of cake to do the combination using the "marching true values" method (there, I made up a name for it)

    Regards,

    Paul McKenzie

  13. #13
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    Sorry to dredge up this thread again, but I noticed a limitation about Paul's code and wondered if anyone knew of a solution that would handle these other cases.

    Specifically, Paul's code assumes unique elements -- i.e. there are no repeated elements. So if I ran Paul's program with the following input:

    Code:
        string alpha = "ABBCCCDD";
        // ...
        int nItems = 3;
    The code produces 56 combinations though 75% of them are repeats. I am looking to find (or make if I have to) code that will produce only the 14 unique combinations.

    Thanks,

    Kevin

  14. #14
    Join Date
    Apr 1999
    Posts
    27,449
    Originally posted by KevinHall
    Sorry to dredge up this thread again, but I noticed a limitation about Paul's code and wondered if anyone knew of a solution that would handle these other cases.
    Well, combinations are only going to work for unique elements. You could std::sort and run std::unique on the elements before getting the combinations.
    Code:
    #include <algorithm>
    #include <string>
    
    std::string GetUnique(const std::string& s)
    {
        std::string temp = s;
        std::sort(temp.begin(), temp.end());
        temp.erase(std::unique(temp.begin(), temp.end()), temp.end());
        return temp;
    }
    
    int main()
    {
        std::string alpha = GetUnique("ABBBCCCDDD");
        int nItems = alpha.length();
        // Now get combinations.
    Regards,

    Paul McKenzie

  15. #15
    Join Date
    Dec 2003
    Posts
    220
    Mr McKenzie !!!

    If I would like to write it in C, how can i change it ? This use of STL just works in WinConsole to test its algorithm.. i mean in case I want to do something in Borland Builder or something to simulate its flow...

    Thanks so much,

    Regards,

    homestead

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured