获取字符串中所有变化字符的组合(c++)

Question

好吧，我已经为这件事折腾了5个小时了。

我对c++还是个新手，如果这是个愚蠢的问题，请原谅我。

我想得到所有可能的字符组合，并把它们放在一个字符串，在c++中。

void changeCharInString(std::string &str, int index, char ch)
{
str[index] = ch;
}
for (int i = 0; i < globals::numOfValidChars; i++)
//numOfValidChars is just sizeof validChars
{
changeCharInString(test, 0, globals::validChars[i]);
//validChars is valid characters, which is an array of lowercase letters and some symbols
//'test' is just my testing string for this.
}

如果我想要一个三个字母的字符串的所有组合，手动，我要做的是:

for (int a = 0; a < globals::numOfValidChars; a++)
{
changeCharInString(test, 0, globals::validChars[a]);
//index 0 because first for loop
//do something with string 'test'
for (int b = 0; b < globals::numOfValidChars; b++)
{
changeCharInString(test, 1, globals::validChars[b]);
//index 1 because second second loop
//do something with string 'test'
for (int c = 0; c < globals::numOfValidChars; c++)
{
changeCharInString(test, 2, globals::validChars[c]);
//index 2 because third for loop
//do something with string 'test'
}
}
}

这将打印"aaa"到"___"('_'是我的validChars数组中的最后一个特殊字符)，包括重复的，例如"aa_","a_a"和"_aa"。

但是，和所有程序员一样，我想要一些效率，而不想自己手动输入for循环。

我的问题:有人有这样做的方法吗?我在谷歌上看到过一些帖子，但我真的不理解它们，包括大多数，如果不是全部，没有副本…

谢谢大家。我希望这篇文章没有给你们阅读带来太多麻烦<3

Answer 1

您将问题标记为"递归"，因此这里有一个使用递归的答案:

void generate(int idx, string& test) {
if (idx == test.size()) {
// do something with test
} else {
for (char c : globals::validChars) {
test[idx] = c;
generate(idx+1, test);
}
}
}

如果大小是固定的，并且在编译时已知，你可以使用模板，如果它不是太大，编译器会为你创建一个很好的嵌套循环:

template <size_t idx>
void generate(string& test) {
for (char c : globals::validChars) {
test[test.size()-idx] = c;
generate<idx-1>(test);
}
}
template <>
void generate<0>(string& test) {
// do something with test
}
int main() {
string test("aaa");
generate<3>(test);
}

Answer 2

就像你说的硬编码方式是这样的

for (char c1 : globals::validChars) {
for (char c2 : globals::validChars) {
for (char c3 : globals::validChars) {
std::string s {c1, c2, c3};
do_job(s);
}
}
}

或range-v3

for (auto t : ranges::view::cartesian_product(globals::validChars,
globals::validChars,
globals::validChars)) {
std::string s{ std::get<0>(t), std::get<1>(t), std::get<2>(t)};
do_job(s);
// std::apply([](auto... args){ std::string s{args...}; do_job(s); }, t); // C++17
}

对于任意大小，可以使用

bool increase(const std::vector<char>& alphabet,
std::string& s,
std::vector<std::size_t>& it)
{
for (std::size_t i = 0, size = it.size(); i != size; ++i) {
const std::size_t index = size - 1 - i;
++it[index];
if (it[index] >= alphabet.size()) {
it[index] = 0;
s[index] = alphabet[it[index]];
} else {
s[index] = alphabet[it[index]];
return true;
}
}
return false;
}
template <typename F>
void iterate(F do_job, const std::vector<char>& alphabet, std::size_t size)
{
std::vector<std::size_t> it(size, 0);
std::string s(size, alphabet[0]);
do {
do_job(s);
} while (increase(alphabet, s, it));
}

演示

Answer 3

您正在描述来自标准算法的next_permutation