next_permutation

View Source

 1# @leet start
 2class Solution:
 3    def nextPermutation(self, nums: list[int]) -> None:
 4        """
 5        This question asks us to transform the input into its "next permutation",
 6        which is the lexicographically larger permutation of its integer.
 7        If that's not possible (i.e. all the numbers are strictly decreasing)
 8        return the original permutation (the one in increasing order).
 9
10        We can do this by looping through the list of numbers twice:
11        First, we want to identify the location where the numbers stop decreasing
12        when iterating from the start.
13
14        Secondly, after we find that number, we want to find a number to swap
15        with. To do so, we iterate from right to left again and try to find
16        the first number that is larger than the number we found in our first
17        loop.
18
19        Afterwards, we swap those numbers, and then reverse the numbers up to
20        our first location, in order to generate the smallest nexct permutation.
21        """
22        n = len(nums)
23
24        i = n - 2
25        while i >= 0 and nums[i] >= nums[i + 1]:
26            i -= 1
27
28        if i >= 0:
29            j = n - 1
30            while nums[j] <= nums[i]:
31                j -= 1
32            nums[i], nums[j] = nums[j], nums[i]
33
34        l, r = i + 1, n - 1
35        while l < r:
36            nums[l], nums[r] = nums[r], nums[l]
37            l += 1
38            r -= 1
39
40
41# @leet end
42
43
44def test():
45    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def nextPermutation(self, nums: list[int]) -> None:
 5        """
 6        This question asks us to transform the input into its "next permutation",
 7        which is the lexicographically larger permutation of its integer.
 8        If that's not possible (i.e. all the numbers are strictly decreasing)
 9        return the original permutation (the one in increasing order).
10
11        We can do this by looping through the list of numbers twice:
12        First, we want to identify the location where the numbers stop decreasing
13        when iterating from the start.
14
15        Secondly, after we find that number, we want to find a number to swap
16        with. To do so, we iterate from right to left again and try to find
17        the first number that is larger than the number we found in our first
18        loop.
19
20        Afterwards, we swap those numbers, and then reverse the numbers up to
21        our first location, in order to generate the smallest nexct permutation.
22        """
23        n = len(nums)
24
25        i = n - 2
26        while i >= 0 and nums[i] >= nums[i + 1]:
27            i -= 1
28
29        if i >= 0:
30            j = n - 1
31            while nums[j] <= nums[i]:
32                j -= 1
33            nums[i], nums[j] = nums[j], nums[i]
34
35        l, r = i + 1, n - 1
36        while l < r:
37            nums[l], nums[r] = nums[r], nums[l]
38            l += 1
39            r -= 1

def nextPermutation(self, nums: list[int]) -> None: View Source

 4    def nextPermutation(self, nums: list[int]) -> None:
 5        """
 6        This question asks us to transform the input into its "next permutation",
 7        which is the lexicographically larger permutation of its integer.
 8        If that's not possible (i.e. all the numbers are strictly decreasing)
 9        return the original permutation (the one in increasing order).
10
11        We can do this by looping through the list of numbers twice:
12        First, we want to identify the location where the numbers stop decreasing
13        when iterating from the start.
14
15        Secondly, after we find that number, we want to find a number to swap
16        with. To do so, we iterate from right to left again and try to find
17        the first number that is larger than the number we found in our first
18        loop.
19
20        Afterwards, we swap those numbers, and then reverse the numbers up to
21        our first location, in order to generate the smallest nexct permutation.
22        """
23        n = len(nums)
24
25        i = n - 2
26        while i >= 0 and nums[i] >= nums[i + 1]:
27            i -= 1
28
29        if i >= 0:
30            j = n - 1
31            while nums[j] <= nums[i]:
32                j -= 1
33            nums[i], nums[j] = nums[j], nums[i]
34
35        l, r = i + 1, n - 1
36        while l < r:
37            nums[l], nums[r] = nums[r], nums[l]
38            l += 1
39            r -= 1

This question asks us to transform the input into its "next permutation", which is the lexicographically larger permutation of its integer. If that's not possible (i.e. all the numbers are strictly decreasing) return the original permutation (the one in increasing order).

We can do this by looping through the list of numbers twice: First, we want to identify the location where the numbers stop decreasing when iterating from the start.

Secondly, after we find that number, we want to find a number to swap with. To do so, we iterate from right to left again and try to find the first number that is larger than the number we found in our first loop.

Afterwards, we swap those numbers, and then reverse the numbers up to our first location, in order to generate the smallest nexct permutation.

def test(): View Source

45def test():
46    assert 2 + 2 == 4