All Combinations of the alphabet - Page 2
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 24 of 24

Thread: All Combinations of the alphabet

  1. #16
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    You could std::sort and run std::unique on the elements before getting the combinations.
    That is actually too restrictive. In my example (3 of "ABBCCCDD"), using std::unique and your code would only provide 4 values:

    B C D
    A C D
    A B D
    A B C

    and is missing values such as:

    A B B
    C C C
    B B D
    B D D
    (and there are six others)

    - Kevin

    P.S. Don't get me wrong. I think your code is great.... I've kept it around b/c it is very useful. It just isn't meeting my needs for one particular problem.

  2. #17
    Join Date
    Apr 1999
    Posts
    27,427
    Originally posted by Homestead
    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
    It works with any C++ compiler that supports STL
    i mean in case I want to do something in Borland Builder or something to simulate its flow...
    Borland Builder is a C++ compiler -- it will work with that also. I don't know what you mean by "write it in 'C' if you are using Borland C++ builder.

    Regards,

    Paul McKenzie

  3. #18
    Join Date
    Apr 1999
    Posts
    27,427
    Originally posted by KevinHall
    That is actually too restrictive. In my example (3 of "ABBCCCDD"), using std::unique and your code would only provide 4 values:
    Then you will have to introduce "uniqueness" into your sequences. By definition, combinations only work on distinct values. Maybe something like this:
    Code:
    #include <algorithm>
    #include <string>
    #include <vector>
    #include <iostream>
    
    #include "combo.h" // The combo generation code
    
    void GenerateUnique(std::vector<int>& v, int size)
    {
        v.resize(size);
        for ( int i = 0; i < size; ++i )
          v[i] = i;
    }
    
    int main()
    {
        std::string sVal = "ABBCCCDD";
        std::vector<int> V;
        GenerateUnique(V, sVal.size());
        CombinationGenerator<int> CG(V, 3);
        std::vector<int> Elements;
        while ( CG.NextCombination(Elements) )
        {
              std::string s;
              for ( int i = 0; i < 3; ++i )
                  cout << sVal[Elements[i]];
              cout << endl;
        }
    }
    Regards,

    Paul McKenzie

  4. #19
    Join Date
    Nov 2003
    Posts
    1,405
    Originally posted by jrlambs
    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.
    All you have to do is to use nested loops. If you have say 10 letters and want all 3-letter groups just,
    Code:
    for (int i=0; i<10; i++)
       for (int j=0; j<10; j++)
          for (int k=0; k<10; k++) 
               // print the i,j,k letter combination
    If you don't want to hardcode the nesting depth you can use recursion. Basically you have a function with one loop. The equivalence of entering a deeper nesting level would be to make a recursive call to that function.

  5. #20
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,565
    As Paul mentioned, maybe put the output into a vector,
    sort the vector, and then remove duplicates using unique:
    Code:
    int main()
    {
        std::string sVal = "ABBCCCDD";
        std::vector<int> V;
        GenerateUnique(V, sVal.size());
        CombinationGenerator<int> CG(V, 3);
        std::vector<int> Elements;
    
        vector<string> vResults;
    
        while ( CG.NextCombination(Elements) )
        {
              std::string s;
              for ( int i = 0; i < 3; ++i )
              {
                  s += sVal[Elements[i]];
              }
              vResults.push_back(s);
        }
    
        sort(vResults.begin(),vResults.end());
        vResults.erase(unique(vResults.begin(),vResults.end()),vResults.end());
    
        copy(vResults.begin(),vResults.end() , ostream_iterator<string>(cout,"\n"));
    
    
        return 0;
    }
    This might not be practical for a very large number of
    combinations. In the case where the number of unique
    elements is very much smaller than the number of
    total elements, it might be more efficient to do a
    custom method: maybe an insertion-sort method, where
    you can use a binary search to see if the element is
    already in the results vector, and add it if not. This will
    require extra copying, but if the number of unique elements
    is relatively small, it might be faster than adding all elements,
    then sorting, then removing duplicates.
    Last edited by Philip Nicoletti; January 7th, 2004 at 11:08 AM.

  6. #21
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    Originally posted by Paul McKenzie
    By definition, combinations only work on distinct values.
    Darn, I knew someone would eventually throw this back at me!

    Originally posted by Philip Nicoletti
    maybe put the output into a vector,
    sort the vector, and then remove duplicates using unique
    That's a little different than Paul's original suggestion, but that is the idea I am currently going with. You're right though that this could be innefficient for large element counts.

    Thanks guys!

    - Kevin

  7. #22
    Join Date
    Jan 2001
    Posts
    251
    To Kevin:

    Starting with Paul's original code, the following seems to work as you want:

    Code:
    int main( int argc, char* argv[] )
       {
       std::string alpha = "ABBCCCDD";
       vector<char> elements(alpha.begin(), alpha.end());
       vector<char> results(alpha.length() + 1, 0);
       vector<char> prevResults;
       
       int nItems = 3;
       CombinationGenerator<char> CG(elements, nItems);
       
       // Call NextCombination until there are no more combinations
       int nTries = 0;
       while (CG.NextCombination(results))
          {
          if ( prevResults == results )
             continue;
    
          // Output our results
          int nSize = results.size();
          for ( int j = 0; j < nSize; j++ )
             cout << results[j] << " ";
          cout << endl;
          nTries++;
    
          prevResults = results;
          }
       
       cout << "Number of combinations is " << nTries << endl;
       
       return 0;
       }
    Because of the way that next_permutation works on the bool vector, the only duplicates that occur are output sequentially, so I just added a check for sequential duplicates.

    To get this to work, any duplicates in the source alpha string must be next to each other, and the number of duplicates must not exceed the output length of the combination string. You could add code which would sort the alpha string and limit the number of duplicates to no more than the requested combination length.

    Best regards,
    John

  8. #23
    Join Date
    Jan 2001
    Posts
    251
    Oops, that didn't work... There are duplicates.

    I guess I would just use a set like this:

    Code:
    int main( int argc, char* argv[] )
       {
       std::string alpha = "ABBCCCDD";
       vector<char> elements(alpha.begin(), alpha.end());
       vector<char> results(alpha.length() + 1, 0);
       
       std::set<vector<char> > prevCombos;
       
       int nItems = 3;
       CombinationGenerator<char> CG(elements, nItems);
       
       // Call NextCombination until there are no more combinations
       int nTries = 0;
       while (CG.NextCombination(results))
          {
          if ( ! prevCombos.insert(results).second )
             continue;
    
          // 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;
       
       return 0;
       }

  9. #24
    Join Date
    Jan 2001
    Posts
    251
    Or an alternate approach (not using Paul's code):

    Code:
    #include <iostream>
    #include <string>
    
    
    using namespace std;
    
    
    void SubDivide( string prefix, string input, int countNeeded )
       {
       // make sure that there is enough string left to complete another combo
       while ( input.size() >= countNeeded )
          {
          // save the current character
          char current = input[0];
    
          // count how many repeats of this letter
          int countStart = input.find_first_not_of( current );
          if ( countStart < 0 )
             countStart = input.size();
    
          // output the combo if long enough
          if ( countStart >= countNeeded )
             cout << prefix << string(countNeeded,current) << endl;
    
          // remove the repeated characters at the start of the string
          input.erase( 0, countStart );
    
          // try a sequence including each possible grouping of the first letter
          int countInit = (countStart >= countNeeded) ? countNeeded-1 : countStart;
          for ( int count = countInit; count > 0; --count )
             SubDivide( prefix + string(count,current), input, countNeeded-count );
          }
       }
    
    
    int main( int argc, char* argv[] )
       {
       SubDivide( "", "ABBCCCDD", 3 );
       
       return 0;
       }
    This is implemented using a recursive approach.
    The input string needs to have all duplicate letters grouped together, but doesn't care about the sort order between different letters.

Page 2 of 2 FirstFirst 12

Posting Permissions

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


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center