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

12 thoughts on “Find all combinations with repetitions (C++)

    Ben Lo said:
    30/10/2015 at 6:25 am

    […] all possible combinations of ABC (e.g. AAA, AAB, AAC, ABA … CCC) which I posted about here ( https://kagato0110.wordpress.com/2015/10/28/find-all-combinations-with-repetitions-c/ ) in Objective-C as a terminal based […]

    stefan d. said:
    07/11/2015 at 2:48 pm

    Simple and cool !
    I am trying to modify your solution to output combinations with repetition without permutation like below (5 elements taken 3 at a time)
    AAA, AAB, AAC, AAD, AAE, ABB, ABC, ABD, ABE, ACC, ACD, ACE, ADD, ADE, AEE, BBB, BBC, BBD, BBE, BCC, BCD, BCE, BDD, BDE, BEE, CCC, CCD, CCE, CDD, CDE, CEE, DDD, DDE, DEE, EEE
    but I am not so successful… Could you please help me?

      Benji responded:
      07/11/2015 at 3:03 pm

      Hi Stefan

      That should be a piece of cake. All you have to do is instead of the char array in my example having 3 chars A, B C you just need to add the extra 2 to have A, B, C, D, E then loop 5 times instead of 3.

      But again having 5 loops bested all together looks ugly so if you want to make your code look neater use recursion.

      Ben

        stefan d. said:
        07/11/2015 at 6:23 pm

        Ben, thanks. It is not just about having extra 2 elements.It is about getting rid of permutations. While in your series you could have AAC, ACA and CAA, in my series there is only AAC (alphabetical order must be respected so each element appears in its alphabetical order, although it can repeat itself in a combination). Still scratching my head 😉 …

    Benji responded:
    07/11/2015 at 7:02 pm

    Hi Stefan

    (well ok speaking from the top of my head and how id do this roughly ) .. You could store each permutation in another array then traverse that after the entire combination of characters have been printed out.

    I’d also write a function to do all this for readability

    Hope this helps 🙂

    Benji responded:
    07/11/2015 at 7:06 pm

    P.s. Inside this function you traverse the newly created array of every permutation. When you traverse through this array you can have like an if statement woth your search criteria

    If (element == "AAC") 
    {
        // do something 
    }
    
      stefan d. said:
      08/11/2015 at 7:49 am

      Ben, thanks so much

    hamlet said:
    24/03/2016 at 10:57 am

    hello , i am trying to build this example with cocos2d, but i don’t know hot to fix position in my app ,migth you a short example of this in cocos2d?

      Benji responded:
      24/03/2016 at 1:58 pm

      Hi Hamlet,
      I’m not sure what you mean by fixing a position in your app .. Can you tell me what you are trying to accomplish? and if you are commenting on the right blog post?

    hamlet said:
    29/03/2016 at 5:15 pm

    hallo , thank for answer me , i am triying of make one combination of 24 sprite with 6 position ,for make a list of all posible combination with the formula n!/(n-r)!(r)! . n=sprites and r=6 position i am using singleton. thas i need to make for make fnish my game and only i can find example with caracter in c++ but is for me dificult . please if have any suggestion. i will greatting very much.

      Benji responded:
      30/03/2016 at 1:32 am

      Hi Hamlet,
      Im having trouble still trying to understand what exactly you are trying to achieve. Can you show me some code on what you’ve done so far?

    hamlet said:
    30/03/2016 at 6:11 am

    hello, i could found this example with character, i am make the same with sprite in cocos2d , i can remplace the vector char for my singleton method called display, but the problem is how the sprite can take position for make the cout? if the vector position here is a unsigned (the singleton method can take inside one Vec2 for take the position in the internal procedure).

    #include
    #include
    #include
    #include

    using std::copy;
    using std::cout;
    using std::endl;
    using std::vector;

    void combinations_recursive(const vector &elems, unsigned long req_len,vector &pos, unsigned long depth,unsigned long margin)
    {
    // Have we selected the number of required elements?
    if (depth >= req_len) {
    for (unsigned long ii = 0; ii < pos.size(); ++ii)
    cout << elems[pos[ii]];
    cout << endl;
    return;
    }

    // Are there enough remaining elements to be selected?
    // This test isn't required for the function to be correct, but
    // it can save a good amount of futile function calls.
    if ((elems.size() – margin) < (req_len – depth))
    return;

    // Try to select new elements to the right of the last selected one.
    for (unsigned long ii = margin; ii < elems.size(); ++ii) {
    pos[depth] = ii;
    combinations_recursive(elems, req_len, pos, depth + 1, ii + 1);
    }
    return;
    }

    void combinations(const vector &elems, unsigned long req_len)
    {
    assert(req_len > 0 && req_len <= elems.size());
    vector positions(req_len, 0);
    combinations_recursive(elems, req_len, positions, 0, 0);
    }

    const unsigned long num_elements = 6;
    const unsigned long comb_len = 5;

    int main()
    {
    //”abcdefghijklmnopqrstuvwx”
    vector elements(num_elements);
    char elements_str[num_elements + 1] = “abcdef”;
    copy(elements_str, elements_str + num_elements, elements.begin());

    combinations(elements, comb_len);
    return 0;
    }

    the singleton metod is:

    #include “Pulsaciones.h”
    #include
    #include
    #include
    #include “cocos2d.h”
    USING_NS_CC;
    using namespace cocos2d;

    Pulsaciones *Pulsaciones::createWithSpriteFrameName(const std::string & spriteFrameName,Vec2 p)
    {
    Pulsaciones *pRet = new Pulsaciones();
    if (pRet && pRet->initWithSpriteFrameName(spriteFrameName,p))
    {
    pRet->autorelease();

    return pRet;
    }

    }
    Pulsaciones * Pulsaciones::pRet=0;
    bool Pulsaciones::initWithSpriteFrameName ( const std::string & spriteFrameName,Vec2 p )
    {
    _speed = p;

    if (Sprite::initWithSpriteFrameName(spriteFrameName)) {
    this->setPosition(p);

    return true;
    }

    }

    Note:
    i need generate one list of all combination of my sprite (24 in total) in 6 space(Vec2) without repetition (the formula for calculate is result= n!/(n-r)!(r)! being n= 24 sprite and r=6 space(Vec2) acording with the equiation result =134,596 combination. then i want to make a unique list with all the combination for make comparition.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s