时间戳

首页 > 解决方案 > 将递归算法生成所有组合转换为迭代

c++ - 将递归算法生成所有组合转换为迭代

问题描述

谁能帮我把这个算法变成一个迭代算法。我知道递归只是迭代加上一个堆栈，但到目前为止我还没有想出一个合适的解决方案。

void rGenCombs(int n, int k, vector<int>& chosen, int idx,
               vector<vector<int>>& combs) {
    if (chosen.size() == k) {
        combs.push_back(chosen);
        return;
    }
    for (int i = idx; i <= n; ++i) {
        chosen.push_back(i);
        rGenCombs(n, k, chosen, i + 1, combs);
        chosen.pop_back();
    }
}

vector<vector<int>> genCombsRec(int n, int k) {
    vector<vector<int>> combs;
    vector<int> chosen;
    rGenCombs(n, k, chosen, 1, combs);
    return combs;
}

更新我现在有这个。问题是我无法弄清楚要编写哪些循环。我猜应该可以通过一个简单的while循环以某种方式实现。

vector<vector<int>> genCombs(int n, int k) {
    vector<int> numStack, chosen;
    vector<vector<int>> combs;
    numStack.push_back(1);
    while (!numStack.empty()) {
        if (chosen.size() == k) {
            combs.push_back(chosen);
            chosen.pop_back();
            continue;
        }
        chosen.push_back(numStack.back());
        if (numStack.back() <= n) {
            numStack.push_back(numStack.back() + 1);
        } else {
            numStack.pop_back();
        }
    }
    return combs;
}

解决方案

对于不需要堆栈的不同迭代算法，我最终得到以下结果：

int getNextIncIndex(const vector<int>& combs, int n) {
    int k = static_cast<int>(combs.size());
    for (int i = k - 1; i >= 0; --i) {
        int distFromRight = k - i - 1;
        if (combs[i] < n - distFromRight) {
            return i;
        }
    }
    return -1;
}

vector<vector<int>> genCombs(int n, int k) {
    vector<vector<int>> combs;
    vector<int> comb(k, 1);
    iota(comb.begin(), comb.end(), 1);
    while (true) {
        for (int i = comb[k - 1]; i <= n ; ++i) {
            comb[k - 1] = i;
            combs.push_back(comb);
        }
        int incIdx = getNextIncIndex(comb, n);
        if (incIdx == -1) {
            break;
        } else {
            iota(comb.begin() + incIdx, comb.end(), comb[incIdx] + 1);
        }
    }
    return combs;
}

标签： c++algorithm

解决方案

我不会给你答案，但我会给你一个关键技巧，让你可以合理地机械地做到这一点。

你的心理障碍的一部分是你有两种类型的控制流交织在一起。第一个是你的for循环。第二个是递归。你如何突破你的for循环内部去到外部循环和递归，只是回到你的for循环内部？很容易混淆。

但改为引入的不是一个，而是两个堆栈。一个堆栈是跟踪您需要执行的操作。另一个用于调用框架中的所有数据。最终代码的关键部分如下所示：

while (0 < actions.size()) {
    action thisAction = actions.pop_back();
    switch (thisAction.type) {
        case ENTER_FUNCTION:
            ...
            break;
        case ENTER_LOOP:
            ...
            break;
        case EXIT_LOOP:
            ...
            break;
        case EXIT_FUNCTION:
            ...
            break;
    }
}

现在您正在以统一的方式跟踪循环和函数调用。没有更多的困惑。

这是您在每个部分中所做的事情。

  • ENTER_FUNCTION：检查你的 if，决定你是否会有一个循环，然后你是否将它设置为开始并附加到ENTER_LOOP你的动作堆栈上。（如果您不循环，则执行 if。）
  • ENTER_LOOP：测试循环条件。如果匹配，则设置循环，并将ENTER_LOOP, EXIT_LOOP, EXIT_FUNCTION,附加ENTER FUNCTION到操作堆栈上。（请注意，堆栈中的最后一项将首先发生。）然后将函数调用的参数添加到调用堆栈上，以便在进行递归调用时它们就在那里。
  • EXIT_LOOP：执行chosen.pop_back()并增加i当前调用框架的一部分。（这很重要，调用帧需要分开！）
  • EXIT_FUNCTION: 去掉顶部的调用框架，就完成了。

一旦你认为你理解了这个策略，就去学习Forth。:-)

推荐阅读