Мне понадобилось какое то время, чтобы понять верный подход к решению, делюсь подробным разбором этой задачи.
Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов.
Например, есть массив [1,2,5,3], предполагается, что функция изменит исходный массив вот так: [1,3,2,5]. Следующий вызов функции для измененного массива выдаст [1,3,5,2] и так далее, пока мы не достигнем состояния [5,3,2,1]. После этого требуется, чтобы функция вернула минимальное состояние, а именно — [1,2,3,5].
Для начала стоит понаблюдать как изменяются состояния, чтобы выдвинуть гипотезы о том, как это работает. Начнем с минимального состояния:
|
1 2 3 4 5 6 7 8 |
1. [1,2,3,5] 2. [1,2,5,3] 3. [1,3,2,5] 4. [1,3,5,2] 5. [1,5,2,3] 6. [1,5,3,2] 7. [2,1,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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// функция меняет исходный массив, // потому ничего не должна возвращать function nextPermutation(nums: number[]): void { // сначала мы находим "точку роста" let i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) i--; // если точка не найдена, это значит, что // мы имеем макс. комбинацию и нужно // выполнить реверс массива, чтобы перейти к минимуму if (i < 0) { nums.reverse() return; } // ищем следующий по порядку элемент в хвосте после // точки роста let best = i + 1, minDelta = nums[best] - nums[i], next = best + 1; while (next < nums.length) { const newDelta = nums[next] - nums[i]; // кандидат должен быть больше, чем элемент точки роста, // но при этом меньше предыдущего кандидата. if (newDelta > 0 && minDelta > newDelta) { minDelta = newDelta best = next; } next ++; } // меняем местами элементы точки роста и // лучшего найденного кандидата [nums[i], nums[best]] = [nums[best], nums[i]]; // сортируем хвост const tail = nums.slice(i + 1).sort((a, b) => a - b); nums.splice(i + 1, Number.MAX_SAFE_INTEGER, ...tail); }; |
