# Efficiently Generate Subset of all Permutations or Combinations with and without Repetition (C++)

Suppose I want to write some functions which return the vector containing a vector representing all permutations or combinations with or without repetition (dependent on the function) of a subset of a given size of a given input vector. Right now, my code is looking like this:

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

template <typename T>
struct permcomb
{
std::vector<std::vector<T>> end_set;
std::vector<T>* data;
permcomb(std::vector<T>& param) : data(&param) {}

void permutation_help(std::vector<T> seen, int recurse_num, bool repetition, bool comb)
{
if(recurse_num == 0)
{
if(end_set.size() > 0 && comb)
{
bool f = false;
for(int i = 0; i < end_set.size(); i++)
{
if(std::is_permutation(end_set[i].begin(), end_set[i].end(), seen.begin()))
{
f = true;
}
}
if(!f)
{
end_set.push_back(seen);
}
}
else // permutations always choose this one
{
end_set.push_back(seen);
}
}
else
{
for(int i = 0; i < (*data).size(); i++)
{
{
seen.push_back((*data)[i]);
permutation_help(seen, recurse_num - 1, repetition, comb);
seen.pop_back();
}
}
}
}
};

// return all permutations no repetition
template <typename T>
std::vector<std::vector<T>> rapnr(std::vector<T>& data, int subset_size)
{
permcomb<T> helpstruct(data);
std::vector<T> empty {};
helpstruct.permutation_help(empty, subset_size, false, false);
return helpstruct.end_set;
}

// return all permutations with repetition
template <typename T>
std::vector<std::vector<T>> rapwr(std::vector<T>& data, int subset_size)
{
permcomb<T> helpstruct(data);
std::vector<T> empty {};
helpstruct.permutation_help(empty, subset_size, true, false);
return helpstruct.end_set;
}

// return all combinations no repitition
template <typename T>
std::vector<std::vector<T>> racnr(std::vector<T>& data, int subset_size)
{
permcomb<T> helpstruct(data);
std::vector<T> empty {};
helpstruct.permutation_help(empty, subset_size, false, true);
return helpstruct.end_set;
}

// return all combinations with repetition
template <typename T>
std::vector<std::vector<T>> racwr(std::vector<T>& data, int subset_size)
{
permcomb<T> helpstruct(data);
std::vector<T> empty {};
helpstruct.permutation_help(empty, subset_size, true, true);
return helpstruct.end_set;
}


This seems to be giving me the right answers so far... but I'm not really happy with the way I went about generating the combinations. Literally the only thing I could think of doing was generating all of the permutations and then eliminating all but one of those which were permutations of each other. This clearly doesn't seem very efficient, but I was at a loss for else I could do. Similarly, I don't feel as I generated the permutations that well either since I always have to go back and search for items that I've already inserted to make sure that I don't insert them again (in the case that repetition isn't allowed). So what steps can I take to optimize what I have so far?

• Perhaps you should include your unit tests in the review, too - that will help us to reproduce your results (validating any suggested changes) and also to suggest testing you may have missed (or identify redundant tests). – Toby Speight Dec 6 '17 at 8:47