代码之家 › 专栏 › 技术社区 › Nils

将生成所有组合的递归算法转化为迭代算法

algorithm c++

-1

Nils · 技术社区 · 6 年前

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

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

2 回复 | 直到 6 年前

btilly 6 年前

我不会给你答案,但我会给你一个关键的诀窍,让你合理地机械地做这件事。

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,决定是否有循环,然后将其设置为start和append ENTER_LOOP 在你的动作堆栈上(如果不循环,则执行If。)
:测试回路条件。如果匹配,则设置循环并附加 进入\u循环 EXIT_LOOP , EXIT_FUNCTION ENTER FUNCTION 在动作堆栈上(请注意,堆栈中的最后一项将首先出现。)然后在调用堆栈中添加函数调用的参数,以便在进行递归调用时它们就在那里。
退出\u循环 chosen.pop_back() 并增加 i 这是你当前通话框架的一部分(这很重要,调用帧需要分开!)
退出功能

一旦你认为你理解了这个策略,就去学习吧 Forth

user58697 6 年前

如果你只需要一个迭代算法,我认为你在寻找一个错误的方向。其实没有必要有一堆。

如果你出于任何原因想要一堆,请忽略其余的。

为了便于说明,我使用 n=6, k=3 :

您可以看到一个简单的模式,这导致了简单的算法:

一旦你到达一个上限,这个位置就不能再增加了,增加下一个“可增加”的位置,然后 std::iota
重新开始,继续前进,直到没有可增加的位置。

这是一个非常肮脏但很有效的实现,有很大的提升空间:

#include <numeric>

int find_incrementable(std::vector<int>& current, int n)
{
    int pos;
    current.push_back(n + 1);   // Dirty hack
    for (pos = current.size() - 2; pos >= 0; --pos) {
        if (current[pos] + 1 < current[pos + 1]) {
            break;
        }
    }
    current.pop_back();
    return pos;
}

std::vector<std::vector<int>> genCombsIter(int n, int k)
{
    std::vector<std::vector<int>> combs;
    std::vector<int> current(k);
    std::iota(current.begin(), current.end(), 1);
    combs.push_back(current);

    int position = k - 1;
    int incrementable;
    while ((incrementable = find_incrementable(current, n)) >= 0) {
        if (incrementable == position) {
            current[position] += 1;
        } else {
            if (incrementable == -1) {
                break;
            }
            std::iota(current.begin() + incrementable, current.end(), current[incrementable] + 1);
            position = k - 1;
        }
        combs.push_back(current);
    }
    return combs;
}