递归生成给定子集大小的所有组合（C++）

Question

请看下面的代码：

#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;
}

运行这段代码会得到以下输出结果：

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

请注意，这段代码并没有实现其所声称要做的事情！它不是返回给定子集大小的所有组合重复的目标，而是返回给定子集大小的所有重复排列。当然，获得组合的方法是生成我所做的所有排列，然后循环遍历以除去那些彼此排列的排列之一。但我相信这绝对不是最有效的方法。

我看到过使用嵌套的for循环来实现这个的方法，但那些方法假设子集大小预先知道。我正在尝试为任何子集大小进行泛化，这就是为什么我试图递归地完成它的原因。问题在于，我不确定我需要如何更改我的递归“helpfunc”才能以有效的方式生成所有组合。

仅澄清一下，预期输出将是这样的：

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

那么，我该如何更改我的代码，以便以高效的方式获取所有带重复的组合，而不是排列？

- ereHsaWyhsipS

---

考虑代码 for( int i = 0; i < 10; ++i ) for( int j = i; j < 10; ++j ) { cout << i << ", " << j << endl; } - Cheers and hth. - Alf

@Cheersandhth.-Alf 这只适用于 subset_size = 2。 - Jon Deaton

输出顺序是否重要？ - Sid S

@JonDeaton：这是一个正确的观察。你认为你能将它推广到其他尺寸吗？ - Cheers and hth. - Alf

@Cheersandhth.-Alf 我也这么认为...我正在努力解决这个问题，我认为这个解决方案是通用的。我们拭目以待。 - Jon Deaton

Answer 1

确保helpfunc循环从当前索引开始，并仅考虑前面的元素。我们不需要后面的元素，因为它们只会是重复的。

#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)
            {
                sizetd::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, int current) // Add one more param for the starting depth of our recursive calls
    {
        if(depth == 0)
        {
            end_set.push_back(seen);
        }
        else
        {
            for(int i = current; i < data.size(); i++) // Set the loop to start at given value
            {
                seen.push_back(data[i]);
                helpfunc(seen, depth - 1, i);
                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, 0); // Initialize the function at depth 0
    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;
}

- super

Answer 2

你可以通过嵌套for循环来解决这个问题，每个循环的计数器从前一个索引到data大小。

for (int i = 0; i < data.size(); i++) {
  for (int j = i; j < data.size(); j++) {
    for (int k = j; k < data.size(); k++) {
      // etc...
  }
}

问题在于循环嵌套的深度等于 subset_size。我们可以通过在循环中进行递归调用来模拟这种任意深度的嵌套：

template <class T>
void solution(std::vector<T>& data, std::vector<std::vector<T>>& sol, int subset_size, int start=0, int depth=0) {
  if (depth == subset_size) return;

  // Assume that the last element of sol is a base vector
  // on which to append the data elements after "start"
  std::vector<T> base = sol.back();

  // create (data.size() - start) number of vectors, each of which is the base vector (above)
  // plus each element of the data after the specified starting index
  for (int i = start; i < data.size(); ++i) {
    sol.back().push_back(data[i]);                   // Append i'th data element to base 
    solution(data, sol, subset_size, i, depth + 1);  // Recurse, extending the new base
    if (i < data.size() - 1) sol.push_back(base);    // Append another base for the next iteration
  }
}

template <typename T>
std::vector<std::vector<T>> permtest(std::vector<T>& data, int subset_size) {
  std::vector<std::vector<T>> solution_set;
  solution_set.push_back(std::vector<T>());
  solution(data, solution_set, subset_size);
  return solution_set;
}

- Jon Deaton