Как сделать перестановку с повторением в C++?

Question

[artyom7777]

Дано число n - кол-во перестановок
2 списка - b, f: b - список видов цифр, f - кол-во повторений этих цифр
Вывести все виды перестановок (повторяться нельзя)
!!!Без nextpermitation, только библиотека iostream + без функций

Answer 1

[Wataru]

Надо руками реализовывать nextpermutation, оно же алгоритм Нарайаны.

Вот есть статья на хабре, даже с кодом, правда на go.

Но сам алгоритм там простой, без труда переведете на си++.

Comments

[artyom7777]

а можно способом, где надо перемещать два элемента в цикле?

[Wataru]

artyom7777, Не понял ваш вопрос.
Самый простой способ - генерировать следующую лексикографически перестановку.
Кажется, есть способы менять местами только 2 соседних элемента и все-равно получить все перестановки без повторений. Обобщение этого метода на перестановки с повторениями мне неизвестны. Возможно, оно даже существует, но будет сильно сложнее предложенного мной алгоритма.

[artyom7777]

пажалуй, вы правы, да какая разница что скажит мой руководитель, я сделал и точка

[artyom7777]

только 1 вопрос, что быстрее ваш код, или который я хотел?

[artyom7777]

просто если он будет очень медленным она меня к чертям размажет

[Wataru]

artyom7777, Я так и не понял, какой код вы хотели.

Если вам надо перестановки вывести, то только сам вывод будет работать за O(n*n!). Алгоритм Нарайаны имеет такую же сложность. Т.е. он не медленнее вывода. Даже если вы найдете какой-то супер-пупер квантовый нереально быстрый алгоритм генерации перестановок, в лучшем случае вы ускорите вашу программу в 2-3 раза.

[artyom7777]

и всё же, можно на всякий случий второй код

[Wataru]

artyom7777, Нет у меня второго кода. Я вообще не знаю, как адаптировать Алгоритм Джонсона-Троттера на перестановки с повторениями.

Не факт, что это вообще возможно.

[artyom7777]

очень жаль =(