Как перебрать все перестановки на C++?

Question

[Leevz]

Реальная задача посложнее, но мне нужно понять лишь сам принцип, поэтому она очень упрощена. Всего есть три типа букв: A, B и C. На вход программы подаются три числа - количество букв A, количество букв B и соответственно C. Как можно перебрать все перестановки (перестановки с математической точки зрения)? Не важно, что с ними делать, выводить, складывать или находить наибольшее, важно, чтобы просто была возможность получить каждую перестановку, а не какие-либо другие комбинации. Сами буквы должны являться элементами массива. Например, на вход подаются числа "1 1 1", поэтому соответствующие комбинации будут: ABC, ACB, BAC, BCA, CAB, CBA. Это простые входные данные, но на практике может быть, например, и такая комбинация чисел - "6 2 3". Не обязательно на C++, но было бы неплохо

Answer 1

[Владимир Олохтонов]

Сведите задачу к более простой: положите все ваши элементы в массив и сгенерируйте все его перестановки.

https://en.cppreference.com/w/cpp/algorithm/next_p...

#include <algorithm>
#include <string>
#include <iostream>
 
int main()
{
    std::string s = "aba";
    std::sort(s.begin(), s.end());
    do {
        std::cout << s << '\n';
    } while(std::next_permutation(s.begin(), s.end()));
}

Comments

[Leevz]

спасибо, это как раз то, что мне нужно. Но не могли бы вы ответить еще на два вопроса? Эта конструкция стоит в условии while, то есть получается, что после переборки всех перестановок, она возвращает 0 (false)? И зачем нужно предварительно отсортировать массив?

[Владимир Олохтонов]

Leevz, сортировка нужна чтобы перестановки шли в лексикографическом порядке.

Да, функция вернёт false когда будет достигнута последняя перестановка, это, кстати, написано по ссылке, код тоже оттуда :)