Какой алгоритм лучше использовать для нахождения всех перестановок?

Question

[Leel Usama]

Дано число: 9202
Нужно составить все возможные комбинации чисел используя цифры данного числа.
К примеру такие тоже подходят:
9022
0922
0292
и т.д.

Что почитать какой алгоритм использовать что бы такое реализовать на JS?

Comments

[Алексей Дубровин]

Кол-во перестановок - Факториал
У вас 4 элемента значит 4!

[hint000]

Алексей Дубровин, неверно.
Факториал - только когда все переставляемые элементы разные. Здесь же цифры могут повторяться.

[Leel Usama]

Нашел алгоритм Нарайаны
https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D...

Мне подходит

[Алексей Дубровин]

hint000, ?
Их 4 штуки.
4 объекта - чтобы посчитать кол-во возможных перестановок это факториал
В вашем примере вы дали вводные данные
9202
Выводные
9022
0922
0292
Из чего следует что это абсолютно подходит.
Если вы про то что 9022 где 2 может поменяться друг с другом.?
Вычтете тогда из результата (факториал суммы элементов - ( факториал(сумма элементов - (кол-во одинаковых повторяющихся элементов -1))
Можно проверить с кол-вом элементов до 5. Если не выдаст ошибок значит будет работать)

[Wataru]

Алексей Дубровин, правильная формула количества чисел тут - n!/(n0!n1!...n9!), где n - длина числа ni - количество цифр i.
Вычитанием вы правильную формулу не получите.

Answer 1

[dollar]

Сначала считаешь количество "мест" и составляешь массив возможных цифр: 0, 2, 9
Причём, для каждой цифры также нужно запомнить, сколько её повторять. В данном примере "2" можно повторить дважды.

Далее в цикле или рекурсией:
на первом месте может быть 0,2,9
на втором месте - уже зависит от первого места (если первое 0, то второе - 2,9, а если первое 2, то второе 0,2,9 и т.д.)
на третьем месте снова выбираешь из оставшихся.
Вот в таком порядке и сможешь вывести все перестановки.

Естественно, код приводить не буду, так как вопрос про алгоритм. Осталось написать в виде текста программы. Удачи)

Answer 2

[Wataru]

В комментариях уже упомянули алгоритм Нарайаны. Он работает с повторяющимеся элементами. Надо найти самый правый элемент строго больший предыдущего, поменять предыдущий с минимальным строго больше его правее и отсортировать массив правее этой позиции (можно перевернуть его).