Как написать алгоритм поиска всех вариантов перестановок?
Дано:
- Массив чисел, длина массива заранее не известна, числа могут повторяться.
- Пример [1,2,6,1,3,1,1,1]
Задача:
- Сгенерировать все возможные перестановки этого массива.
- Комбинации не должны повторяться (для массива [1,2,1] это [2,1,1],[1,2,1],[1,1,2]).
- Решение должно быть оптимальным. Вариант с прямым перебором комбинаций элементов займет N! даже если в массиве есть повторяющиеся элементы.
Что уже пробовал:
- Рекурсивный алгоритм перебора сочетаний элементов массива (N!).
- Тот же алгоритм переписанный на хвостовую рекурсию (N!).
- Алгоритм тасования, там много времени расходуется что бы понять уникальная новая комбинация или нет.
Хотелось бы получить такой алгоритм, который на каждом следующем шаге, путем перестановки 2х или более элементов, будет выдавать новую уникальную комбинацию до тех пор, пока комбинации не кончатся и мы не получим исходную комбинацию.
Если я правильно понял код, тут мы перебираем все возможные варианты перестановок и на каждом шаге просто проверяем уникальность комбинации. Вариант не плох, но на достаточно большом массиве сломается. Поправьте меня, если ошибаюсь.
