@pacan4ik

Как решать задачи на перебор массива n*n количества раз без повторений значений?

Уже второй раз попадается задача, где нужно перебрать массив с получением максимально возможных комбинаций его значений
Например ['a', 'b', 'c', 'd']
Нам нужно получить все возможные комбинации строк с этими буквами

Есть похожая задача и с числами, где ещё нужно уметь написать так, чтобы не было повторов (без new Set)
Я не совсем пока понял, как сделать это цикл с множеством само создающихся циклов и то этот вариант не решит оптимизацию получения ответа без повторов.

Есть название подхода к решению подобных задач?
  • Вопрос задан
  • 64 просмотра
Решения вопроса 1
sergiks
@sergiks Куратор тега JavaScript
♬♬
само создающихся циклов

Вероятно, вас интересует рекурсия.

Один из алгоритмов получения всех перестановок использует рекурсивный вызов функции.

Логика такая: на первой позиции может побывать каждая из букв. На остальных – все перестановки оставшихся.

Например, взяли первую 'a' и остался массив на 1 короче: ['b', 'c', 'd']
С этим укороченным подход точно такой же, как с исходным: на 1-й позиции по очереди каждая. И ротация оставшихся двух. Для двух — то же самое. Т.е. это реализуется одной и той же функцией, только на входе массивы разной длины.
И в конце цепочки вызовов на вход приходит массив с единственным символом – тут сразу возвращается он.

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

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

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