Мне понадобилось какое то время, чтобы понять верный подход к решению, делюсь подробным разбором этой задачи.
Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов.
Например, есть массив [1,2,5,3], предполагается, что функция изменит исходный массив вот так: [1,3,2,5]. Следующий вызов функции для измененного массива выдаст [1,3,5,2] и так далее, пока мы не достигнем состояния [5,3,2,1]. После этого требуется, чтобы функция вернула минимальное состояние, а именно — [1,2,3,5].
Для начала стоит понаблюдать как изменяются состояния, чтобы выдвинуть гипотезы о том, как это работает. Начнем с минимального состояния:
Просматривая каждый раз массив с конца, мы находим место где i-й элемент меньше i + 1. Я назвал это место «точкой роста».
В этой точке нужно i-й элемент заменить на следующий по порядку, выбирая из тех, что следуют за ним. Сам i-й элемент и оставшиеся далее в хвосте сортируются по порядку возрастания.
Например, в строке 4, точка роста — это элемент 3 (i = 1). Выбирая следующий по порядку (т.е. > 3) из хвоста [5, 2], мы имеем только один вариант — элемент 5. Этот элемент переходит на позицию i = 1, и у нас остается хвост из набора [3, 2]. Их мы сортируем, выстраивая по порядку [2, 3]. Так у нас получается следующая комбинация (шаг №5) — [1, 5, 2, 3].
Сортировка нужна, чтобы получить комбинацию чисел не просто больше предыдущей, а именно ближайшую следующую для заданной.
Если логика понятна, то перейдем к коду. Вариант на TS.