维护递归计数

发布于 2024-10-18 07:08:53 字数 1522 浏览 3 评论 0原文

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

我编写了一个函数,用所有排列填充队列,但我似乎不知道如何保持准确的计数。

最终,我希望该函数返回由 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();
}

I'm trying to count the number of calls within a recursive permutation function.

I've written a function that fills a queue with all the permutations but I can't seem to figure out how to maintain an accurate count.

Ultimately i'd like the function to return a subset of the permuatations specified by lbound and ubound arguments, and to do so I think i need someway to keep an internal count.

Using the size of the returned queue will not work since i'd like the function to be able to handle permutations too big to hold in memory.

For this code i'd like the count to be returned as 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();
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

朦胧时间 2024-10-25 07:08:53

使用静态计数是行不通的,因为它永远不会被重置(如果您使用多线程,则会导致问题)。

相反,这样怎么样:

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

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

    return count;
}

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

Using a static count will not work, because it's not going to ever be reset (and will cause problems if you ever go multi-threaded).

Instead, how about this:

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

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

    return count;
}

Each call to Permutation() returns the total number of calls that were made below it in the call tree. As we unwind, all the counts from the sub-trees get summed together, to eventually produce the final return value.

只为一人 2024-10-25 07:08:53
int foo(int count,/*Other Params*/) {
/*Calucation*/
 if (!terminatingCondition) {
  foo(count++,/*Other Params*/);
 }
 logger.log("foo was called " + count + "times");
 return /*calcualtion*/;
}
int foo(int count,/*Other Params*/) {
/*Calucation*/
 if (!terminatingCondition) {
  foo(count++,/*Other Params*/);
 }
 logger.log("foo was called " + count + "times");
 return /*calcualtion*/;
}
天涯离梦残月幽梦 2024-10-25 07:08:53

我只是想通过忽略你的实际算法目的来回答这个问题。这两个静态值应该移至参数引用,否则您没有一个好的方法来重置它们的值。

void Permutations(vector<vector<int>> param, vector<vector<int>> &perm, vector<int> &iter, int &count, int index=0)
{
    ++count;
    // ...
}

I'm just trying to answer the question by ignoring your actual algorithm purpose. The two statics should be moved to argument references, or you don't have a good way to reset their values.

void Permutations(vector<vector<int>> param, vector<vector<int>> &perm, vector<int> &iter, int &count, int index=0)
{
    ++count;
    // ...
}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文