# Iteratively generating permutations with repetitions

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. 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. 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$. Apr 25, 2019 at 9:34

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
Apr 25, 2019 at 13:01

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

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