31. Следующая перестановка (Next Permutation)

Задание.

Перестановка массива целых чисел – это расположение его элементов в последовательности или линейном порядке.

• Например, для arr = [1,2,3], ниже приведены все перестановки arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

Следующая перестановка массива целых чисел – это следующая лексикографически большая перестановка его целого числа.

Более формально: если все перестановки массива отсортированы в одном контейнере в соответствии с их лексикографическим порядком, то следующая перестановка этого массива – это перестановка, которая следует за ней в отсортированном контейнере.

Если такое расположение невозможно, массив должен быть переставлен в минимально возможном порядке (т.е. отсортирован в порядке возрастания).

• Например, следующая перестановка arr = [1,2,3] равна [1,3,2].

• Аналогично, следующая перестановка arr = [2,3,1] равна [3,1,2].

• В то время как следующая перестановка arr = [3,2,1] равна [1,2,3], потому что [3,2,1] не имеет лексикографической более крупной перестановки.

Итак, да массив целых чисел nums

Нужно найти следующую перестановку в nums.

Замена нужно сделать на месте (in-place) и нужно использовать только постоянную дополнительную память.

Пример 1.

Входные данные: nums = [1,2,3]

Результат: [1,3,2]

Пример 2.

Входные данные: nums = [3,2,1]

Результат: [1,2,3]

Пример 3.

Входные данные: nums = [1,1,5]

Результат: [1,5,1]

Решение.

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
    	int n = nums.size(), k, l;
    	for (k = n - 2; k >= 0; k--) { // поиск убывающей последовательности
            if (nums[k] < nums[k + 1]) {
                break;
            }
        }
    	if (k < 0) {
    	    reverse(nums.begin(), nums.end());
    	} else {
    	    for (l = n - 1; l > k; l--) { // поиск крайнего правого преемника для поворота
                if (nums[l] > nums[k]) {
                    break;
                }
            }
    	    swap(nums[k], nums[l]);
    	    reverse(nums.begin() + k + 1, nums.end());
        }
    }
};

Алгоритм

Согласно Википедии, человек по имени Нараяна Пандита представил следующий простой алгоритм для решения этой проблемы в 14 веке.

1. Нужно найти наибольший индекс k такой, что nums[k] < nums[k + 1]. Если такого индекса не существует, нужно просто перевернуть nums и готово.

2. Нужно найти наибольший индекс l > k такой, что nums[k] < nums[l].

3. Нужно поменять местами nums[k] и nums[l].

4. Нужно перевернуть подмассив nums[k + 1:].

Иллюстрация