这个算法叫什么名字——递归算法？

Question

有必要构建值键的所有组合：

输入：

data["key1"] = {"value1", "value2", "value3"};
data["key2"] = {"value4", "value5"};
data["key3"] = {"value6"};

输出：

"value1"   "value4"   "value6"
"value1"   "value5"   "value6"
"value2"   "value4"   "value6"
"value2"   "value5"   "value6"
"value3"   "value4"   "value6"
"value3"   "value5"   "value6

”

为此我有一个递归函数，一个递归组合。那里使用的算法的名称是什么？

#include <QMap>
#include <QList>
#include <QString>
#include <QDebug>

typedef QMap<QString, QList<QString>> SubPluralsShema;

void recursiveCombination(const SubPluralsShema& data, QStringList currentCombination, const QStringList& keys, int keyIndex) {
    if (keyIndex == keys.size()) {
        for (const QString& value : currentCombination) {
            qDebug() << value << " ";
        }
        qDebug() << "\n";
        return;
    }

    const QString& key = keys[keyIndex];
    const QList<QString>& values = data[key];

    for (const QString& value : values) {
        currentCombination.append(value);
        recursiveCombination(data, currentCombination, keys, keyIndex + 1);
        currentCombination.removeLast();
    }
}

int main() {
    SubPluralsShema data;

    // Fill the data structure for the example
    data["key1"] = {"value1", "value2", "value3"};
    data["key2"] = {"value4", "value5"};
    data["key3"] = {"value6"};

    QStringList keys = {"key1", "key2", "key3"};
    QStringList currentCombination;

    recursiveCombination(data, currentCombination, keys, 0);

    return 0;
}

我不会低估为什么它的代码：“currentCombination.removeLast();”

Answer 1

首先关注

recursiveCombination()

顶层调用的for循环（keyIndex=0）：

• 它将

  value1

  添加到列表中。
• 使用 keyIndex=1 调用

  recursiveCombination()

  并通过值

  传递 

  currentCombination ，因此您的本地

  currentCombination

  在返回时将仅保留

  value1

  。
• 现在您的下一次迭代想要处理

  value2

  ，因此您需要从列表中删除

  value1

  。

一般来说，循环将当前列表 (

data[keys[keyIndex]]

) 中的值添加到

currentCombination

，并调用

recursiveCombination()

来处理其余的键。在开始循环的下一次迭代之前，需要删除该值。