C++ Code to Generate Permutations [closed]

Question

I am trying to code a program that will generate permutations with the characters repeated. So far I have 3 loops:

for (int f = 0; f < n; f++)
    for (int s = 0; s < n; s++)
        for (int t = 0; t < n; t++)
            newString = characters[f] + characters[s] + characters[t];

This approach lacks generality in that it requires me to know the permutation length beforehand.

Example: ABC

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 

Any help would be appreciated.

Thanks,

Answer 1

If you need permutations (your example is not permutations), C++ Standard Library has a perfect function for that - std::next_permutation:

string s("ABC");
do {
    cout << s << endl;
} while (next_permutation(s.begin(), s.end()));

Note that the range must be sorted coming into the first iteration of this loop in order to generate a complete list of permutations (Demo #1).

Your example produces all combinations with repetitions from a set of characters. You can do it with nested loops, like you did, or with recursion:

void combinations(const string& s, vector<int>& pos, int n) {
    if (n == s.size()) {
        for (int i = 0 ; i != n ; i++) {
            cout << s[pos[i]];
        }
        cout << endl;
        return;
    }
    for (int i = 0 ; i != s.size(); i++) {
        pos[n] = i;
        combinations(s, pos, n+1);
    }
}

Demo #2.