Как сделать эту функцию рекурсивной

Question

void print_combinations(const std::string &str)
{
        int i, j, k;
        int len = str.length();

        for (i = 0; i < len - 2; i++)
        {
                for (j = i + 1; j < len - 1; j++)
                {
                        for (k = j + 1; k < len; k++)
                                // show combination
                                cout << str.at(i) << str.at(j) << str.at(k) << endl;

                }
        }
}

Эта функция делает то, что я хочу, но я хочу сделать ее рекурсивной, чтобы она могла создавать комбинации произвольной длины.

Answer 1

Существует алгоритм STL для получения перестановок , который вы можете использовать для этого.Создайте вектор целых чисел (не bools, это зло), и предоставьте кучу единиц (в вашем примере три из них), за которыми следует достаточно нулей, чтобы равняться длине строки.Затем используйте алгоритм перестановки, чтобы пройти все перестановки этого вектора.Используя каждую из этих перестановок, распечатайте строковые символы, которые соответствуют символам в векторе:

for (int i = 0; i < string.length(); i++)
{
  if (v[i]) cout << string.at(i);
}
cout << endl;
next_permutation(v.begin(), v.end());

Answer 2

Ваш вопрос немного напоминает домашнее задание, поэтому я только предлагаю подход:

void print_combinations_internal(
    std::string const& str,
    std::string & prefix,
    int start_at,
    int remaining_levels)
{
    if (remaining_levels<=0) {
        cout << prefix << '\n';
    } else {
        ...
        loop / recursive call
        ...
    }
}

void print_combinations(const std::string &str, int length)
{
    std::string temp; // initially empty
    print_combinations_internal(str,temp,0,length);
}

Answer 3

Это мое решение (мне нужно было кое-что подготовить для тяжелого дня:)

#include <iostream>
#include <string>

void print_combinations(const std::string &str)
{
        int i, j, k;
        int len = str.length();

        for (i = 0; i < len - 2; i++)
        {
                for (j = i + 1; j < len - 1; j++)
                {
                        for (k = j + 1; k < len; k++)
                                std::cout << str.at(i) << str.at(j) << str.at(k) << std::endl;

                }
        }
}

void print_rec(const std::string &str, int currLevel, int totalLevel, int startPos, std::string tempString)
{
    if (currLevel == totalLevel)
    {
        std::cout << tempString << std::endl;
        return;
    }

    for (unsigned int i = startPos; i < str.length() - totalLevel + currLevel + 1; i++) 
    {
        tempString.push_back(str.at(i));
        print_rec(str, currLevel + 1, totalLevel, i + 1, tempString);
        // tempString.pop_back();
        tempString.erase(tempString.length() -1, tempString.length());
    }
}

int main() 
{
    print_combinations("testing");
    std::cout << std::endl << "====================" << std::endl << std::endl;
    std::string tempString = "";
    print_rec("testing", 0, 3, 0, tempString);
}

выход:

tes
tet
tei
ten
teg
tst
tsi
tsn
tsg
tti
ttn
ttg
tin
tig
tng
est
esi
esn
esg
eti
etn
etg
ein
eig
eng
sti
stn
stg
sin
sig
sng
tin
tig
tng
ing

====================

tes
tet
tei
ten
teg
tst
tsi
tsn
tsg
tti
ttn
ttg
tin
tig
tng
est
esi
esn
esg
eti
etn
etg
ein
eig
eng
sti
stn
stg
sin
sig
sng
tin
tig
tng
ing

Answer 4

Вот попытка:

#include <iostream>
#include <string.h> // for strlen
#include <stdlib.h> // for atoi
#include <sstream>
void expand_combinations(const char *remaining_string, std::ostringstream& i, int remain_depth)
{
    if(remain_depth==0)
    {
        std::cout << i.str() << std::endl;
        return;
    }

    for(int k=0; k < strlen(remaining_string); ++k)
    {
        std::ostringstream l;
        l << i.str();
        l << remaining_string[k];
        expand_combinations(remaining_string+k+1, l, remain_depth - 1);
    }
    return;
}
int main(int argc, char **argv)
{
    std::ostringstream i;
    if(argc<3) return 1;
    expand_combinations(argv[1], i, atoi(argv[2]));
    return 0;
}

Выход ./test фьорд 3:

fjo
fjr
fjd
for
fod
frd
jor
jod
jrd
ord