Перестановка по массиву символов

Question

Предположим, вам нужно обнаружить все возможные перестановки 'n' различных символов, например 'a', 'b', 'c'. Можете ли вы предложить алгоритм, который я могу использовать, чтобы это сделать? Вообще-то, как бы вы это сделали?

Answer 1

Let 'Perms' - это набор найденных перестановок, а «Used» - список выбранных символов.

Чтобы найти перестановок п символов из множества S:

1. Если п = 0, то используется подстановка. Добавьте его в Пермь и верните.
2. Для каждого полукокса C в S:
   1. Remove C из S и добавить (или толкать) его U.
   2. Найти перестановки N-1 символов из S.
   3. Удалить конец (или поп) U и добавить C к S.

Когда вы вернулись от поиска перестановок п символов, завивка содержит все возможные перестановки.

Обратите внимание, что все это делается с использованием наборов и списков. Есть альтернативы с более легким весом, но эти структуры делают шаги более простыми, поэтому я их использовал.

Answer 2

Существует реализация Java here.