Function to find all combinations with repetitions [duplicate]

Question

This question already has answers here:

Creating all possible k combinations of n items in C++ (14 answers)

Closed 9 years ago.

I have this function:

    void permutate (const string & s, std::vector<int>& index, std::size_t depth, int & count)
    {
        if (depth == s.size())
        {
            ++count;
            for (std::size_t i = 0; i < s.size(); ++i)
            {
                cout << s[index[i]];
            }
            cout << "\n";
            return;
        }

    for (std::size_t i = 0; i < s.size(); ++i)
    {
        index[depth] = i;
        permutate(s, index, depth + 1, count);
    }
}

To print all combinations I use this:

void print(string s) {

    if (s.find_first_not_of(s.front()) == string::npos)
    {
        cout << "Only 1 combination exists";
        return;
    }

    sort(s.begin(), s.end());

    cout << s << "\n**********\n";

    vector<int> index(s.size());
    int count = 0;

    permutate(s, index, 0, count);

    cout << "\nTotal combinations with repetitions: " << count;
}

Functions work great but I need specific combinations. For example, if I write

print("ABC");

I get: AAA, AAB, AAC, ABA, ..., CCA, CCB, CCC. So, I get overall 27 combination. But what if I need to make combination which size is not as the one of original set (in this case, size of original set is 3)?

For example, if I have a string "ABC" (or a set S = {A, B, C}) and I want combinations of size 2, I should get exactly 9 combinations: AA, AB, AC, BA, BB, BC, CA, CB, CC.

Please suggest changes that should be made in order to achieve my goal. Thank you.

!!! Edit:

I want the same result as here but in C++.

Answer 1

I think the best solution is typeing new code in with you use backtrack for permutations. I typed something like that you should provide vector V with chars you want for combinations and call the function bactrack like bactrack(0,length_of_expected_string). You will got permutations in set S in alphaetical order. You can uncommet code for typenig combinations on a screen.

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<string>
#include<stack>
#include<list>
#include<vector>
#include<math.h>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<ctime>
#include<map>
#include<set>
using namespace std;

vector<char> V;
vector<char> combination;
set<vector<char> > S;
void backtrack(int depth,int expected_length)
{
if(depth<expected_length)
{
    for(int i=0;i<V.size();i++)
    {
        combination.push_back(V[i]);
        backtrack(depth+1,expected_length);
        combination.pop_back();
    }
}
else
{
    /*for(int i=0;i<combination.size();i++)
    {
        cout<<combination[i];
    }
    cout<<endl;*/
    S.insert(combination);
}
}

int main()
{
backtrack(0,3);
for(auto it=S.begin();it!=S.end();it++)
{
    /*
    for(int i=0;i<(*it).size();i++)
    {
        cout<<(*it)[i];
    }
    cout<<endl;*/
}
}