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

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

Вот попробовать:

#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 

Answer 2

an STL algorithm to get permutations, который вы могли бы использовать для этого. Создайте вектор ints (not bools, the evil) и предоставите кучу из них (в вашем примере три из них), за которым следует достаточное количество нулей, чтобы равняться длине строки. Затем используйте алгоритм перестановки для прохождения всех перестановок этого вектора. Использование каждого из этих перестановок, распечатать строки символов, которые соответствуют те, в векторе:

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

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

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

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