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&lt;int&gt;&amp; perm, vector&lt;vector&lt;int&gt;&gt;&amp; perms, int n, int m) {
    if (perm.size() == n) {
        perms.push_back(perm);
        return;
    }
    for (int i = 0; i &lt; 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&lt;vector&lt;int&gt;&gt; genAllPerms(int n, int m) {
    vector&lt;vector&lt;int&gt;&gt; perms;
    vector&lt;int&gt; perm(1, 0);
    int i = 0;
    while (!perm.empty()) {
        if (perm.size() == n) {
            perms.push_back(perm);
            if (perm.back() &lt; 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 :)
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 &lt;vector &lt;int&gt; &gt; genperms(int n,int m) {
    vector &lt;vector&lt;int&gt;&gt; perms;
    vector &lt;int&gt; curr(n,1);
    perms.push_back(curr);
    while(true){
        int change = 0;
        for(int i=n-1;i&gt;=0;i--){
            if(curr[i] &lt; m){
                curr[i]++;
                for(int j=i+1;j&lt;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.