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).
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;
// Output our results
int nSize = results.size();
for ( int j = 0; j < nSize; j++ )
cout << results[j] << " ";
cout << endl;
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.
Last edited by Paul McKenzie; April 21st, 2003 at 04:42 AM.
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).
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.
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:
The next combination would be ---CD-F
Permute the bools:
The next combination would be --CDE-
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)
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...