每一个最后的组合都是双基础 C++

Question

我想要一个 return 字母 X 的所有可能组合的函数，这些组合必须有 n 长。我知道这已经完成了一百万次了，但我试图理解递归。

两件事我不明白：

一个。该函数将系列的每个最后一次迭代插入两次，因此如果字母表为 'AB' 并且长度为 2，我希望：

AA
AB
BA
BB

但我得到：

AA
AB
AB
BA
BB
BB

和 2.函数怎么可能需要外层循环中的return。如果我只是删除外循环并保留 return 那么我会得到分段错误。

在我保留矢量的函数中，我也可以把它放在全局范围内，但我有同样的效果。我即时构建可能的组合 S 并保持 len en 深度：

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

void combirec(vector<string> &A, char S[20], char *alphabet, int len, int depth)
{
    for (int i = 0; i < len; i++) {
        for (int c = 0; c < strlen(alphabet); c++) {
            S[depth] = alphabet[c];
            combirec(A, S, alphabet, len-1, depth+1);
            A.push_back(S);
        }
        return;
    }
}

int main()
{
    vector<string> A;
    char S[20];
    char alphabet[6] = "AB";
    int len = 2;
    S[len] = '[=12=]';
    combirec(A, S, alphabet, len, 0);
    for (int i = 0 ; i < A.size(); i++)
        cout << A[i] << endl;
}

Answer 1

您的问题是同时具有循环和递归：

void combirec(vector<string> &A, char S[20], char *alphabet, int len, int depth)
{
    for (int i = 0; i < len; i++) {//<--LOOP HERE
        for (int c = 0; c < strlen(alphabet); c++) //{<--LOOP HERE
            S[depth] = alphabet[c];
            combirec(A, S, alphabet, len-1, depth+1);//<--RECURSIVE HERE
            A.push_back(S);
        }
        return;
    }
}

如果你不想递归，你可能最多需要一个循环。

对于类似的问题，请参阅此答案：

Creating all possible k combinations of n items in C++

Answer 2

一些有用的建议导致了解决方案，但我仍然不清楚为什么会这样。我自己永远不会想出这个。

void combirec(vector<string> &A, char S[20], char *alphabet, int len, int depth)
{
    if (len > 0)
        for (int c = 0; c < strlen(alphabet); c++) {
            S[depth] = alphabet[c];
            combirec(A, S, alphabet, len-1, depth+1);
        }
    else
        A.push_back(S);

}

每一个最后的组合都是双基础 C++

Every last combination is double basic C++

c++

recursion

cartesian-product