How to make this function recursive

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;

                }
        }
}

This function does what I want, but I want to make it recursive, so that it can create combinations of arbitrary length.

Answer 1

There is an STL algorithm to get permutations that you could use for this. Create a vector of ints (not bools, those are evil), and provide a bunch of ones (in your example three of them) followed by enough zeros to equal the length of the string. Then use the permutation algorithm to go through all the permutations of that vector. Using each of these permutations, print out the string characters that correspond to the ones in the vector:

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

Here is a try:

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

Output of ./test fjord 3:

fjo
fjr
fjd
for
fod
frd
jor
jod
jrd
ord

Answer 3

This is my solution (I needed something to worm up for the hard day:)

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

output:

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

Your question feels a bit like a homework question which is why I'm only suggesting an approach:

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