@leelusama
Junior Frontend developer

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

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

Что почитать какой алгоритм использовать что бы такое реализовать на JS?
  • Вопрос задан
  • 406 просмотров
Пригласить эксперта
Ответы на вопрос 2
dollar
@dollar
Делай добро и бросай его в воду.
Сначала считаешь количество "мест" и составляешь массив возможных цифр: 0, 2, 9
Причём, для каждой цифры также нужно запомнить, сколько её повторять. В данном примере "2" можно повторить дважды.

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

Естественно, код приводить не буду, так как вопрос про алгоритм. Осталось написать в виде текста программы. Удачи)
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
В комментариях уже упомянули алгоритм Нарайаны. Он работает с повторяющимеся элементами. Надо найти самый правый элемент строго больший предыдущего, поменять предыдущий с минимальным строго больше его правее и отсортировать массив правее этой позиции (можно перевернуть его).
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы