Разрешить повторения в этом генераторе перестановок
У меня есть следующий генератор перестановок:
#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» могут разрешать перестановки, подобные следующим:
ааЪ
ааа
акк
Решение
Вы можете использовать следующие для 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));
}
Другие решения
Других решений пока нет …