self study

Find all combinations with repetitions (C++)

Posted on Updated on

One of the most mind boggling (yet very simple) programming problems I’ve found recently was to write a program that displays all combinations of a string with repetitions.

Lets say you have an array like so:

char _chars[] = {'A', 'B', 'C'};

Now write a function that creates the output like so:

AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC

So how would we do this?
I would first store the char array into a vector like so:

std::string _tmpStr;
for (int i = 0; i < 3; i++)
{
     _tmpStr += _charArray[i];
}
std::vector<int> pos(_tmpStr.size(), 0);
Hoge::CombinationSequence(_tmpStr, pos, 0);  // call function to find all combinations

And somewhere in the source code I have declared and called the function like so:

/**
 *	可能な全ての組み合わせがを出力する
 */
void Hoge::CombinationSequence(const string& v, std::vector<int>& pos, int n)
{
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = 0; j < v.size(); j++)
        {
            for (int k = 0; k < v.size(); k++)
            {
                cout << v[i] << v[j] << v[k] << " ";
            }
    }
}

Compiling and running this produces the output we expect.

Problem:
What if the input data increases by size?
How do we calculate a string of data that is maybe 100 elements long instead of 3?

Solution:
The simplest solution is to just add more for loops. But having 100 for loops is a pain in the butt. So Instead, we can use recursion, to call the function itself however times necessary. This means that the input data can change size and our function will automatically loop to different sized arrays, achieving a dynamic design.. Like so:

/**
 *	可能な全ての組み合わせがを出力する
 */
void Hoge::CombinationSequence(const string& v, std::vector<int>& pos, int n)
{
    if (n == v.size())
    {
        for (int i = 0; i != n; i++)
	{
	    cout << v[pos[i]];
	}
	cout << " ";
	return;
    }

    // Loop through the vector and update position to whichever element it is pointing to. Then pass that reference back to our function so we know which letter it is referring to.
    for (int i = 0; i != v.size(); i++)
    {
        pos[n] = i;
        Hoge::CombinationSequence(v, pos, n + 1);
    }
}

Hope this helps somebody out there. The solution was quite simple it didn’t even occur to me how simple it was.

By the way,
A, B, C = 3 types of data
3 x 3 = 9
9 x 3 = 27

We have with this example, 27 possible combinations.

Advertisements