如何使这个函数递归

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 算法来实现此目的。创建一个整数向量（不是布尔值，它们是邪恶的），并提供一堆（在您的示例中为三个），后跟足够的零以等于字符串的长度。然后使用排列算法遍历该向量的所有排列。使用这些排列中的每一个，打印出与向量中的字符相对应的字符串字符：

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

这是一个尝试：

#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 fjord 3 的输出：

fjo
fjr
fjd
for
fod
frd
jor
jod
jrd
ord

Answer 3

你的问题感觉有点像一个家庭作业问题，这就是为什么我只建议一种方法：

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 4

这是我的解决方案（我需要一些东西来度过艰难的一天：）

#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