Разрешить повторения в этом генераторе перестановок

У меня есть следующий генератор перестановок:

#include <iostream>
#include <string>

using std::string;
using std::cout;

void comb(string sofar, string rest, int n)
{
std::cout << "comb('" << sofar << "', '" << rest << "', " << n << ")\n";
string substring;

if (n == 0)
cout << sofar << '\n';
else {
for (size_t i = 0; i < rest.length(); i++) {
substring = rest.substr(0, i) + rest.substr(i + 1, rest.length());
comb(sofar + rest[i], substring, n - 1);
}
}
}

int main()
{
comb("", "abcde", 3);

return 0;
}

Как я могу настроить его, чтобы учесть повторяющиеся элементы?
Например, перестановки для параметров «abcde» могут разрешать перестановки, подобные следующим:

ааЪ

ааа

акк

-1

Решение

Вы можете использовать следующие для cartesian_product

bool increase(const 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] >= s.size()) {
it[index] = 0;
} else {
return true;
}
}
return false;
}

void do_job(const std::string& s,
const std::vector<std::size_t>& it)
{
for (std::size_t i = 0; i != it.size(); ++i) {
std::cout << s[it[i]] << " ";
}
std::cout << std::endl;
}

void cartesian_product(const std::string& s, std::size_t n)
{
std::vector<std::size_t> it(n, 0u);

do {
do_job(s, it);
} while (increase(s, it));
}

демонстрация

0

Другие решения

Других решений пока нет …