All Combinations of the alphabet

[jrlambs]

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

[Luis G]

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.

[Paul McKenzie]

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:

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).

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.

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

[CBasicNet]

jrlambs :If you intend to get all combinations as you stated, there are total of 66 million different combinations.

Here's an article (http://www.codeguru.com/algorithms/combination.html) written by me. Hope it helps.

[mwilliamson]

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

[Paul McKenzie]

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

[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.

thanks for all your hlp so far!

Jeff

[Paul McKenzie]

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

[Paul McKenzie]

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

[Luis G]

He probably saw it on mine, not yours.

[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

[Paul McKenzie]

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

[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.

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:

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

[Paul McKenzie]

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.

#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

[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.. i mean in case I want to do something in Borland Builder or something to simulate its flow...

Thanks so much,

Regards,

homestead

[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 algorithmIt 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.