Генерация перестановок с повторениями
Условия задачи: Язык C++. Есть 6 этажей (ну или 6 этапов если так можно выразиться). На каждом можно вставить буквы A B C D, но с каждым этапом количество слотов увеличивается на 1, начиная с первого.
Расположение буквы в слотах относительно других букв не имеет значения, т.е. ААB и ABA и т.д. - одно и то же. Важен лишь сам факт присутствия этих букв в слотах (так как потом с ними будут производиться определенные действия, ну что-то вроде за каждую букву А добавить к NUM +1, за каждую букву B добавить к NUM +2 и т.д.)
Задача: Сгенерировать все возможные комбинации перестановок, подпадающих под эти условия. Если можно, еще добавить по возможности count с количеством суммарно сгенерированных вариантов.
Небольшой пример:
A, B, C, D.
AA,AB,AC,AD,BB,CB,DB,CC,DC,DD.
AAA,AAB,AAC ...
...
...
AAAAAA,AAAAAB,AAAAAC и т.д.
Хотелось бы как-то с использованием метода next_permunation, но он, насколько я понял, генерирует только без повторений, ну или может и с повторениями, но я не смог придумать, как это "прикрутить" это к данной задаче. Даже с вложенными друг в друга циклами у меня не получилось. Помогите, пожалуйста, с этой задачкой.
Ответы (2 шт):
Попробуйте сделать с тремя вложенными циклами. Вначале имеется N однобуквенных строк, комбинации первого уровня, например, "A", "B", "C", "D"
Внешний цикл по длинам комбинаций, начиная с двойки.
Второй цикл по набору строк предыдущего уровня.
Для каждой строки запускается третий цикл, перебирающий символы начиная с последнего символа текущей строки до последнего из возможных, и добавляющий этот символ в конец строки. Из "AAB", например, получаются строки AABB,AABC,AABD, складываются в список комбинаций данного уровня.
Вот и все.
Рекурсивно:
vector<string> generation(size_t N, const string& A)
{
vector<string> s;
if (N == 1)
{
for(auto c: A) s.emplace_back(1,c);
return s;
}
for(auto r: generation(N-1,A))
{
for(auto c: A) s.push_back(r + c);
}
return s;
}
int main(int argc, char * argv[])
{
for(int n = 2; n < 7; ++n)
{
cout << n << ":\n";
for(auto r: generation(n,"ABCD")) cout << r << " "; cout << "\n";
}
}