Алгоритм генерации всех перестановок путем выбора некоторых или всех символов
=============================================================================

Мне нужно сгенерировать все перестановки строки с выбором некоторых элементов. Например, если в моей строке "abc", вывод будет {a, b, c, ab, ba, ac, ca, bc, cb, abc, acb, bac, bca, cab, cba}.

Я подумал о базовом алгоритме, в котором я генерирую все возможные комбинации «abc», которые представляют собой {a, b, c, ab, ac, bc, abc}, а затем переставляет их все.

Так есть ли эффективный алгоритм перестановки, с помощью которого я могу генерировать все возможные перестановки с переменным размером.

Код, который я написал для этого:

Мне нужно использовать хеш для избежания одной и той же комбинации, поэтому, пожалуйста, дайте мне знать, как я могу улучшить этот алгоритм.

Спасибо, Г.Г.

 что вы можете написать программу намного быстрее, чем уже. Основная проблема - размер вывода: он имеет порядок`n!*2^n` (количество подмножеств * среднее количество перестановок для одного подмножества), которое уже`> 10^9` для строки из 10 разных символов.

С СТЛ`next_permutation` добавляет очень ограниченную сложность для таких маленьких строк, временная сложность вашей программы уже почти`O(output size)`.

Но вы можете сделать свою программу немного проще. Особенно,`for( k =1; k<=n; k++)` цикл кажется ненужным: вы уже вычисляете размер подмножества в переменной`c` внутри. Так что просто`int k = c` вместо`if (c == k)`, (Вам также необходимо рассмотреть случай пустого подмножества:`i == 0`)

**редактировать**  
На самом деле, есть только 9864100 выходов для`n == 10` (не`~ 10^9`). Тем не менее, моя точка зрения остается неизменной: ваша программа уже тратит впустую только время "O (next\_permutation)" для каждого вывода, что очень и очень мало.



видеть это[Алгоритм возврата всех комбинаций k элементов из n](https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n)

очень подробные решения вашей проблемы



 но вы можете добавить цикл для работы с переменным размером. Или просто храните в комплекте, чтобы исключить лишние дубликаты для вас: