3
\$\begingroup\$

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++)
      {
        if(repetition || find(seen.begin(), seen.end(), (*data)[i]) == seen.end()) // if not found
        {
          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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Toby Speight Dec 6 '17 at 8:47
1
\$\begingroup\$

I'm going to focus on the algorithmic aspects of your code rather than the style, as I don't know C++. You want to generate permutations and combinations with unique elements, so all you need to do is find the sublist of unique elements, and find the permutations and combinations of that. To uniquify, you should use a structure with a fast contains method (tree or hash set), and add each element is the vector to it if it isn't already. This will use O(n) memory, but your output is much later, so that overhead is justified given that it will save a lot of time later.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.