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:

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:

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

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

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.

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.

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

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

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)

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.

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.

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