Генерация перестановок с повторениями

Рейтинг: -2Ответов: 2Опубликовано: 03.03.2023

Условия задачи: Язык 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, но он, насколько я понял, генерирует только без повторений, ну или может и с повторениями, но я не смог придумать, как это "прикрутить" это к данной задаче. Даже с вложенными друг в друга циклами у меня не получилось. Помогите, пожалуйста, с этой задачкой.

c# перестановка
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

Рекурсивно:

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";
    }
}
▲ 0

Попробуйте сделать с тремя вложенными циклами. Вначале имеется N однобуквенных строк, комбинации первого уровня, например, "A", "B", "C", "D"

Внешний цикл по длинам комбинаций, начиная с двойки.

Второй цикл по набору строк предыдущего уровня.

Для каждой строки запускается третий цикл, перебирающий символы начиная с последнего символа текущей строки до последнего из возможных, и добавляющий этот символ в конец строки. Из "AAB", например, получаются строки AABB,AABC,AABD, складываются в список комбинаций данного уровня.

Вот и все.