c++ - 维护递归计数

Question

我正在尝试计算递归置换函数中的调用次数。

我编写了一个函数，用所有排列填充一个队列，但我似乎无法弄清楚如何保持准确的计数。

最终我希望该函数返回由 lbound 和 ubound 参数指定的排列的子集，为此我认为我需要以某种方式保持内部计数。

使用返回队列的大小将不起作用，因为我希望该函数能够处理太大而无法保存在内存中的排列。

对于此代码，我希望计数返回为 100。

#include <vector>
#include <iostream>;

using namespace std;

int& Permutations(vector<vector<int>> param, vector<vector<int>> &perm, int index=0)
{
    static vector<int> iter;
    static int count = 0;

    if (index == param.size())
    {
        perm.push_back(iter);   // add permutation to queue
        count++;
        return count;
    }

    for (int i=param[index][0]; i<=param[index][1]; i+=param[index][2])
    {
        if (iter.size() > index) iter[index] = i;
        else iter.push_back(i);
        Permutations(param, perm, index+1); // recursive function
    }
}

void main()
{
    vector<vector<int>> params; // vector of parameter vectors

    vector<int> param1, param2;

    int arr1[3] = {0,9,1};  // range for each parameter vector
    int arr2[3] = {0,9,1};  // specified as lbound, ubound, step

    param1.insert(param1.end(),arr1,arr1+3);
    param2.insert(param2.end(),arr2,arr2+3);

    params.push_back(param1);
    params.push_back(param2);

    vector<vector<int>> queue;  // queue of generated permutations

    int permcount = Permutations(params,queue);

    cout << "the permutation count is " << permcount << endl;
    cin.get();
}

Answer 1

使用static 计数是行不通的，因为它永远不会被重置(并且如果你使用多线程会导致问题)。

相反，这个怎么样:

int Permutation(/* params */)
{
    int count = 1;  // Count ourself

    for (whatever)
    {
        count += Permutation(whatever);  // Count cumulative sum from recursion
    }

    return count;
}

每次调用 Permutation() 都会返回调用树中下方的调用总数。当我们展开时，子树的所有计数都会加在一起，最终产生最终的返回值。