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

• R Sahu: Please update your posted code to make it a complete program that one can build and test your functions.
• CiaPan: 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: 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\$.

Answer 1

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.

• Nils: Also looking at this 18 days later this seems to be easier to understand.

Answer 2

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:
4. 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().

• Nils: You mean here: while (perm.back() == m) { perm.pop_back(); } Yep that is a bug I should have called empty() first!