防止递归组合生成中的内存分配

Question

（抱歉这个标题，这不是最好的描述）

我正在研究图论，并生成一组给定输入数字的所有可能组合。给定输入集 {2,3,4}，我可能的组合（其中有 3!）是：

以下递归解决方案有效，但我不喜欢这样的事实，即我必须 "copy" 输入向量才能 "remove" 表示我正在跟踪的节点的元素以防止再次将其包含在输出中。我要输出的元素存储在 vecValues 而我当前可以选择的元素存储在 vecInput:

void OutputCombos(vector<int>& vecInput, vector<int>& vecValues)
{
    // When hit 0 input size, output.
    if (vecInput.size() == 0)
    {
        for (int i : vecValues) cout << i << " ";
        cout << endl;
    }
    size_t nSize = vecInput.size();
    for (vector<int>::iterator iter = begin(vecInput); iter != end(vecInput); ++iter)
    {
        auto vecCopy = vecInput;
        vecCopy.erase(find(begin(vecCopy), end(vecCopy), *iter));
        vecValues.push_back(*iter);
        OutputCombos(vecCopy, vecValues);
        vecValues.pop_back();
    }
}

void OutputCombos(vector<int>& vecInput)
{
    vector<int> vecValues;
    OutputCombos(vecInput, vecValues);
}

int main()
{
    vector<int> vecInput{ 2,3,4 };
    OutputCombos(vecInput);
    return 0;
}

正如我的状态 space 树所预期的那样，输出是

2 3 4 2 4 3 3 2 4 3 4 2 4 2 3 4 3 2

我怎样才能解决这个问题而不必为每个递归调用制作向量的副本？

Answer 1

您总是可以只使用 <algorithm>

中的 std::next_permutation


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

int main()
{
  std::vector<int> input {2, 3, 4};

  do {
        for (auto i : input) std::cout << i << " ";
        std::cout << std::endl;
     }  while(std::next_permutation(input.begin(), input.end()));

    return 0;
}

这给你相同的输出。您可能想查看 next_permutation 的 a possible implementation，它涉及向量内的交换而不是多次复制向量。

Answer 2

经过大量研究，我在 this article 中找到了灵感，这给了我最终的解决方案。这个想法是我们保留一个 Boolean 值的向量，它指示组合中是否使用了特定值；这样我们就不需要删除我们已经使用过的元素，因此没有内存分配开销。

因此，在构建分支 {2,4,3} 时，如果我们到达 {2,4}，vecTaken 将是 {true, false, true}，而 nNumBoolsSet 将是 2。所以当我们循环时，我们只会 "use" vecInput 的索引 1 处的元素，因为这是唯一没有按照 vecTaken.

指示使用的元素

void OutputCombos(vector<int>& vecInput, vector<int>& vecValues, vector<bool>& vecTaken, int& nNumBoolsSet)
{
    size_t nSize = vecInput.size();
    if (nNumBoolsSet == nSize)
    {
        for (int i : vecValues) cout << i << " ";
        cout << endl;
        return;
    }
    for (vector<int>::size_type i = 0; i < nSize; ++i)
    {
        if (vecTaken[i] == false)
        {
            vecValues.push_back(vecInput[i]);
            vecTaken[i] = true;
            ++nNumBoolsSet;
            OutputCombos(vecInput, vecValues, vecTaken, nNumBoolsSet);
            vecTaken[i] = false;
            vecValues.pop_back();
            --nNumBoolsSet;
        }
    }
}

void OutputCombos(vector<int>& vecInput)
{
    vector<int> vecValues;
    vector<bool> vecTaken(vecInput.size(), false);
    int nNumBoolsSet = 0;
    OutputCombos(vecInput, vecValues, vecTaken, nNumBoolsSet);
}

int main()
{
    vector<int> vecInput{ 2,3,4 };
    OutputCombos(vecInput);
}

Answer 3

我认为这可能更接近您要查找的内容。没有 std::next_permutation 的版本不涉及复制任何向量，并允许输入保持 const。但是，这样做的代价是在每次迭代中检查输出以确保它不会两次添加相同的数字。

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

template<typename T>
void OutputCombinations(
    const std::vector<T>& input,
    std::vector<typename std::vector<T>::const_iterator >& output)
{
  for(auto it = input.begin(); it != input.end(); ++it)
  {
    if (std::find(output.begin(), output.end(), it) == output.end())
    {
      output.push_back(it);
      if (output.size() == input.size())
      {
        for(auto node : output) std::cout << *node << " "; 
        std::cout << std::endl;
      }
      else OutputCombinations(input, output);

      output.pop_back();
    }
  }
}

int main()
{
  std::vector<int> nodes{ 2, 3, 4, 2 };
  std::vector<std::vector<int>::const_iterator> result{};
  OutputCombinations(nodes, result);

  return 0;
}

防止递归组合生成中的内存分配

Prevent memory allocation in recursive combination generation

c++

recursion

graph-theory