vendredi 5 janvier 2018

Recursively Generate all Combinations of given Subset Size (C++)

Observe the following code:

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

template <typename T>
void print_2d_vector(std::vector<std::vector<T>>& v)
{
  for(int i = 0; i < v.size(); i++)
  {
    std::cout << "{";
    for(int j = 0; j < v[i].size(); j++)
    {
      std::cout << v[i][j];
      if(j != v[i].size() - 1)
      {
        std::cout << ", ";
      }
    }
    std::cout << "}\n";
  }
}

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

  void helpfunc(std::vector<T>& seen, int depth)
  {
    if(depth == 0)
    {
      end_set.push_back(seen);
    }
    else
    {
      for(int i = 0; i < (*data).size(); i++)
      {
        seen.push_back((*data)[i]);
        helpfunc(seen, depth - 1);
        seen.pop_back();
      }
    }
  }
};

template <typename T>
std::vector<std::vector<T>> permtest(std::vector<T>& data, int subset_size)
{
  permcomb2<T> helpstruct(data);
  std::vector<T> empty {};
  helpstruct.helpfunc(empty, subset_size);
  return helpstruct.end_set;
}

using namespace std;
int main()
{
  std::vector<std::string> flavors {"Vanilla", "Chocolate", "Strawberry"};
  auto a1 = permtest(flavors, 2);

  cout << "Return all combinations with repetition\n";
  print_2d_vector(a1);
  return 0;
}

Running this code results in the following output:

Return all combinations with repetition
{Vanilla, Vanilla}
{Vanilla, Chocolate}
{Vanilla, Strawberry}
{Chocolate, Vanilla}
{Chocolate, Chocolate}
{Chocolate, Strawberry}
{Strawberry, Vanilla}
{Strawberry, Chocolate}
{Strawberry, Strawberry}

Notice how this code does NOT do what it claims to do! Instead of returning all combinations with repetition of a given subset size (the goal), it instead returns all permutations with repetition of a given subset size. Of course, a way to obtain the combinations would be to generate all of the permutations as I have done, and then loop through to remove all but one of those which are permutations of each other. But I'm confident that this is absolutely NOT the most efficient way to do this.

I've seen ways which use nested for loops to achieve this, but those assume that the subset size is known ahead of time. I'm trying to generalize it for any subset size, hence why I'm trying to do it recursively. The issue is that I'm not quite sure how I need to change my recursive "helpfunc" in order to generate all of the combinations in a way that's efficient.

Just to clarify, the expected output would be this:

Return all combinations with repetition
{Vanilla, Vanilla}
{Vanilla, Chocolate}
{Vanilla, Strawberry}
{Chocolate, Chocolate}
{Chocolate, Strawberry}
{Strawberry, Strawberry}

So how can I change my code to obtain all combinations with repetition instead of the permutations in a way that's efficient?

Aucun commentaire:

Enregistrer un commentaire