Каждая последняя комбинация является двойным базовым C ++

Question

Мне нужна функция, которая возвращает все возможные комбинации алфавита X, комбинации должны быть длиной n.Я понимаю, что это было сделано миллион раз прежде, но я пытаюсь понять рекурсию.

Две вещи, которые я не понимаю:

Одна.Функция вставляет каждую последнюю итерацию ряда дважды, поэтому, если алфавит равен 'AB', а длина равна 2, я бы ожидал:

AA
AB
BA
BB

, но я получаю:

AA
AB
AB
BA
BB
BB

и 2Как функция может требовать возврата во внешнем цикле.Если я просто удаляю внешний цикл и оставляю return, то я получаю ошибку сегментации.

В функции, которую я держу при себе, я мог бы также поместить его в глобальную область видимости, но эффект тот же.Я строю возможную комбинацию S на лету и сохраняю большую глубину:

#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] = '\0';
    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)
{
    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);

}

Answer 2

Ваша проблема в том, что есть и циклы, и рекурсия:

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

Если вы не хотите рекурсии, вам, вероятно, потребуется не более одного цикла.

См. Этот ответ для аналогичной проблемы:

Создание всех возможных k комбинаций из n элементов в C ++