Iteratively generating permutations with repetitions

Question

I tried to solve the simple problem of generating all permutations of length n with m distinct elements where repetition is allowed. Doing this recursively took me like 10 minutes:

void genAllPermsRec(vector<int>& perm, vector<vector<int>>& perms, int n, int m) {
    if (perm.size() == n) {
        perms.push_back(perm);
        return;
    }
    for (int i = 0; i < m + 1; ++i) {
        perm.push_back(i);
        genAllPermsRec(perm, perms, n, m);
        perm.pop_back();
    }
}

I tried to do it iteratively then and it took me a lot longer. I ended up looking exactly at what happens in the recursive version and came up with the following solution:

vector<vector<int>> genAllPerms(int n, int m) {
    vector<vector<int>> perms;
    vector<int> perm(1, 0);
    int i = 0;
    while (!perm.empty()) {
        if (perm.size() == n) {
            perms.push_back(perm);
            if (perm.back() < m) {
                perm.pop_back();
                ++i;
                continue; // That is why Python has the while: .. else: construct.
            }
            while (perm.back() == m) { perm.pop_back(); }
            if (!perm.empty()) {
                perm.back() += 1;
                i = 0;
            }
        } else { perm.push_back(i); }
    }
    return perms;
}

It seems to work but I am not satisfied with the result. I suspect that there is a more intuitive way to approach the problem that would lead to shorter code. Please enlighten me :)

Please update your posted code to make it a complete program that one can build and test your functions. — R Sahu
– R Sahu, Commented Apr 7, 2019 at 5:03
The recursive version seems to generate permutations of \$m+1\$ values: the loop for (int i = 0; i < m + 1; ... iterates from i==0 up to i==m. Either start with i=1 or proceed while i < m. — CiaPan
– CiaPan, Commented Apr 25, 2019 at 6:06
Apparently same applies to the iterative version: it starts with zeros and increments values up to m, so it finds permutations of \$m+1\$ values, not \$m\$. — CiaPan
– CiaPan, Commented Apr 25, 2019 at 9:34

score 1 · Accepted Answer · 2019-04-25 08:48:41Z

I think a first problem is that m should be changed to m-1. Or maybe better you should change it so that the lines "i=0;" are changed to "i=1;" instead, and also initializing the vector with 1 instead of 0.

By what I understand a permutation does not necessarily contain each number at least once. So we just need to generate all possible vectors of length \$n\$ with elements in the set \$ \{1,2,\dots, m\}\$.

Your method is the same thing I would do, except I would not use pop_back and instead I would just modify the elements in place (although this is really a small change):

vector <vector <int> > genperms(int n,int m) {
    vector <vector<int>> perms;
    vector <int> curr(n,1);
    perms.push_back(curr);
    while(true){
        int change = 0;
        for(int i=n-1;i>=0;i--){
            if(curr[i] < m){
                curr[i]++;
                for(int j=i+1;j<n;j++){
                    curr[j] = 1;
                }
                change = 1;
                perms.push_back(curr);
                break; //try to change again
            }
        }
        if(change == 0) break; //if we couldnt make a change we are done
    }
    return perms;
}

This modification seems to give like an 8% boost in speed in my computer (using the n=8,m=8 case) . Although probably one can get better improvements if a vector is changed for something else.

If you want to speed this up you can also reserve the outer "perms" vector to a large enough size.

Also looking at this 18 days later this seems to be easier to understand. — Nils
– Nils, Commented Apr 25, 2019 at 13:01

CiaPan · Accepted Answer · 2019-04-25 07:01:28Z

Your use of the i variable isn't clear to me.

The algorithm might look like this (starting with an empty permutation):

Repeat 'forever' (precisely: until a break):
if the permutation isn't full yet (length less than n), append zeros (or whatever the minimum allowed value is);
otherwise:
1. add the permutation to results,
2. remove the tail of maximum values (m in your code, although I suppose it should be m-1),
3. if the permutation is empty, it was mm...m hence we're done - exit;
4. otherwise increment the last element, and continue the loop to fill the tail with zeros.

The implementation below has the condition in the main if negated and if/else clauses swapped when compared to algo above, so the program structure is more similar to yours:

vector<vector<int>> genAllPerms(int n, int m) {
    vector<vector<int>> perms;
    vector<int> perm;
    const int MinVal = 0;
    const int MaxVal = m;    // (m+1) different values allowed

    while (true) {
        if (perm.size() == n) {
            perms.push_back(perm);
            while (!perm.empty() && perm.back() == MaxVal) {
                perm.pop_back();
            }
            if (perm.empty())
                break;
            perm.back() += 1;
        }
        else { perm.push_back(MinVal); }
    }
    return perms;
}

Note: back() has nothing to return from an empty vector - test it with empty() before calling back().

You mean here: while (perm.back() == m) { perm.pop_back(); } Yep that is a bug I should have called empty() first! — Nils
– Nils, Commented Apr 25, 2019 at 13:05

Stack Exchange Network

Iteratively generating permutations with repetitions

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Iteratively generating permutations with repetitions

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions