c++ - 防止在递归组合生成中分配内存

Question

(对不起标题，这不是最好的描述)

我正在玩图论，并生成一组给定输入数字的所有可能组合。给定输入集{2,3,4}，我可能的组合(其中有3!)是:



以下递归解决方案有效，但是我不喜欢必须“复制”输入 vector 才能“删除”表示我要跟随的节点的元素，以防止再次将其包含在输出中这一事实。我要输出的元素存储在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;
}

正如我的状态空间树所预期的那样，输出为
2 3 4
2 4 3
3 2 4
3 4 2
4 2 3
4 3 2
我如何解决这个问题而不必为每个递归调用复制 vector ？

Answer 1

您总是可以只使用std::next_permutation中的<algorithm>

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

这将为您提供相同的输出。您可能想 check out next_permutation的 a possible implementation，它涉及 vector 内的交换，而不是多次复制 vector 。