<jupyter_start><jupyter_text>Next PermutationImplement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.If such an arrangement is impossible, it must rearrange it to the lowest possible order (i.e., sorted in ascending order).The replacement must be in place and use only constant extra memory. Example 1:- Input: nums = [1,2,3]- Output: [1,3,2] Example 2:- Input: nums = [3,2,1]- Output: [1,2,3] Example 3:- Input: nums = [1,1,5]- Output: [1,5,1]  Constraints:- 1 <= nums.length <= 100- 0 <= nums[i] <= 100 Solution InuitionIn order to find the next greater permutation for the array [a1, a2, ..., an], we have to find the min number which is greater then the ak wher k E {1...n}. And thus the idea, is to move backwords on the input array and insert each item to the sorted array. Before inserting we can query if there elements in sorted array that are greater then the current element. If true, we will pick the smallest one and swap. and sort<jupyter_code>def find_larger_right(nums) -> int:
    for i in range(len(nums) - 1, -1, -1):
        if i > 0 and nums[i] > nums[i-1]:
            return i - 1
    return -1

def sort_from_index(idx, nums):
    for i in range(idx, len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] > nums[j]:
                nums[i], nums[j] = nums[j], nums[i]

def next_perm(nums: list):
    idx = find_larger_right(nums)
    sort_from_index(idx + 1 if idx > -1 else 0, nums)

    if idx > -1:
        for i in range(idx + 1, len(nums)):
            if nums[idx] < nums[i]:
                nums[idx], nums[i] = nums[i], nums[idx]
                break


nums = [1, 2, 3]
next_perm(nums)
assert nums == [1,3,2]

nums = [3, 2, 1]
next_perm(nums)
assert nums == [1,2,3]

nums = [1, 1, 5]
next_perm(nums)
assert nums == [1,5,1]

nums = [1, 2]
next_perm(nums)
assert nums == [2, 1]

nums = [1, 3, 2]
next_perm(nums)
assert nums == [2,1,3]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1305668016194332, 'fraction_numerical': 0.03694331983805668, 'mean_word_length': 3.1885593220338984, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '188326', 'license': 'MIT', 'n_tokens_mistral': 757, 'n_tokens_neox': 708, 'n_words': 265, 'path': 'python-data-structures/leetcode/next-permutation.ipynb', 'repo_name': 'dimastatz/ml-workshop', 'size': '1976'}