All permutations of integer vector

Question

I have spent a decent amount of (waaay too much) time trying to write the below function and get my head around recursion. The aim was to return all permutations of an int vector (assuming no duplications of input). I would like to know people's thoughts on my code. One downfall that I can identify is that it is pretty demanding of space since I am copying choice and out vectors many times.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

void uni_permutes(std::vector<int> in, std::vector<int> out, std::vector<int> choice)
{
    int size = choice.size();
    //complete when all ints in choice have already been used
    if(size == 0) {
        for(int i : out) {
        std::cout << i << std::endl;
    }
        std::cout << '\n' << std::endl;
        return;

    }
    std::vector<int> newo = out;
    std::vector<int> newc = choice;
    for (int i : choice) {
        newo.push_back(i);
        //remove i from choice      newc.erase(std::remove(newc.begin(), newc.end(), i), newc.end());
        uni_permutes(in,newo, newc);
        newc = choice;
        newo = out;
} 
    return;
}

int main()
{
    std::vector<int> v1 = {0, 1,2,3};
    std::vector<int > out;    
    uni_permutes(v1,out,v1);

    return 0;
}

Answer 1

Here are my comments:

1. You should be passing in and choice as const reference to avoid unnecessary copies.
2. size should be of type size_t. In general, make sure you take care of whatever warnings the compiler throws at you.
3. Before we even come to algorithmic performance: are you sure this code works? I just did a bit of mental debugging, and it seems like you'll have an infinite recursion, since choice's size will never be zero. I'll assume for now that you accidentally commented out the line that erases from choice.
4. You have a defect in the code: consider a vector of [1, 1, 2, 2]. You'll return two permutations of [1, 2] [2, 1], while presumably you need [1 1 2 2] [1 2 1 2] etc. etc. This is because you delete all members of the same value from the vector rather than just delete at one index.
5. Indeed, there's way too much copying going on. If your goal is just to print all the permutations, or send them to some kind of consumer, then you should preallocate a single out vector, and replace members at given positions as you go through your recursion.