One method to generate all the combinations is to treat this as a number counting program.
The Counting Algorithm
Let's take the case of "digits": a, b, c, and d.
The first number is: aaaa. Much like decimal: 0000.
The second number is: aaab. Decimal: 0001.
The third number is: aaac, decimal: 0002.
The fourth number is: aaad, decimal: 0003.
This process is known as incrementing, e.g. adding a constant value each time.
Now comes the tricky part, incrementing the last digit. According to number counting rules, when the last digit is reached, the last digit is replaced by the first and the digit in the next column is replaced. This is equivalent of a decimal number incrementing from 09 to 10.
So in the example above, the next number in the sequence is: aaba.
This is known as carry, as you are carrying the overflow to the next digit.
Converting Algorithm to Code
Looks like there is a loop to count from first digit to last digit:
#define MAXIMUM_DIGIT_POSITIONS 4
const char FIRST_CHAR = 'a';
const char LAST_CHAR = 'd';
std::vector<char> number(MAXIMUM_DIGIT_POSITIONS); // Reserve some slots.
void Print_Number(const std::vector<char>& number);
int main(void)
{
// Initialize the number
int position = 0;
for (position = 0; position < MAXIMUM_DIGIT_POSITIONS; ++position)
{
number.push_back(FIRST_CHAR);
}
Print_Number(number);
// Loop: incrementing
position = MAXIMUM_DIGIT_POSITIONS - 1; // Because arrays are zero based indexing
while (number[position] < LAST_CHAR)
{
number[position] = number[position] + 1; // Increment to next digit, same position.
Print_Number(number);
}
// Pause before closing
std::cout << "Paused. Press ENTER to close.\n";
std::cin.ignore(100000, '\n');
return EXIT_SUCCESS;
}
void Print_Number(const std::vector<char>& number)
{
for (std::vector<char>::const_iter iter = number.begin();
iter != number.end();
++iter)
{
std::cout << *iter;
}
cout << "\n";
}
Handling Carry
The above program demonstrates counting in a single column. But how to handle the incrementing of the last digit?
Looks like we need to increment the digit in the previous position.
Looking ahead, the value in the previous column will be incremented, until it too, needs to be increment. Thus the carry will be propagate to the previous column. Looks like another loop:
// Loop: number of positions
int propagation_position = position - 1;
while (propagation_position >= 0)
{
while (number[position] < LAST_CHAR)
{
number[position] = number[position] + 1; // Increment to next digit, same position.
Print_Number(number);
}
// Propagate the carry.
while (propagation_position >= 0)
{
if (number[propagation_position] != LAST_CHAR)
{
++number[propagation_position];
number[propagation_position + 1] = FIRST_CHAR;
break;
}
--propagation_position;
}
position = 0;
}
The above new fragment has an outer while loop and a second inner while loop. The outer while loop controls the digit position. The second inner while loop handles the carry.
The whole program is designed so that you can adjust the number of digit positions and the number of digits in the sequence.
Summary
The brute force method for printing all the combinations is like counting numbers. The same principles apply: when the last digit is incremented, it is replaced by the first digit and the digit of the next column is incremented. This is repeated until all positions have been counted.
Walk through the above code with debugger or pen and paper to find any defects and understand the algorithm.
After you understand the algorithm, search your favorite C++ reference for "c++ combination permutation algorithm".
