2
\$\begingroup\$

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 :)

\$\endgroup\$
  • \$\begingroup\$ Please update your posted code to make it a complete program that one can build and test your functions. \$\endgroup\$ – R Sahu Apr 7 at 5:03
  • \$\begingroup\$ 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. \$\endgroup\$ – CiaPan Apr 25 at 6:06
  • \$\begingroup\$ 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\$. \$\endgroup\$ – CiaPan Apr 25 at 9:34
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ +1 for the suggestion to modify in place \$\endgroup\$ – Nils Apr 25 at 12:47
  • \$\begingroup\$ Also looking at this 18 days later this seems to be easier to understand. \$\endgroup\$ – Nils Apr 25 at 13:01
1
\$\begingroup\$

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

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

  1. Repeat 'forever' (precisely: until a break):
  2. if the permutation isn't full yet (length less than n), append zeros (or whatever the minimum allowed value is);
  3. 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().

\$\endgroup\$
  • \$\begingroup\$ You mean here: while (perm.back() == m) { perm.pop_back(); } Yep that is a bug I should have called empty() first! \$\endgroup\$ – Nils Apr 25 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.