All Combinations of the alphabet

[KevinHall]

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.

[Paul McKenzie]

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

[Paul McKenzie]

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:

#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

[_uj]

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,

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.

[Philip Nicoletti]

As Paul mentioned, maybe put the output into a vector,
sort the vector, and then remove duplicates using unique:

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.

[KevinHall]

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

[jwbarton]

To Kevin:

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

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

[jwbarton]

Oops, that didn't work... There are duplicates.

I guess I would just use a set like this:

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;
   }

[jwbarton]

Or an alternate approach (not using Paul's 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.