Why do slicing and sorted fail to reverse list in place?

Question

I am doing the NextPermutation problem on LeetCodeN(https://leetcode.com/problems/next-permutation/). The problem needs me to sort in-place. Here's the problem (Source: LeetCode):

"Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 "[the end]

Tried nums = nums[::-1] and nums = sorted(nums) and both failed the test case nums = [3,2,1] because the array appears to be unsorted. I also printed nums after these assignments and stdout is [1,2,3], which is correct. This error does not make sense because the last line of code nums[inverse_pt+1:] = sorted(nums[inverse_pt+1:]) modified my list as intended. Lastly, I tried nums.sort(), which sorts in-place, and this worked out.

I've read threads on reverse list, slicing.

def nextPermutation(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    if not nums or len(nums) == 1:
        return 
    # find inverse pt
    # O(1) because only 1 variable declared
    inverse_pt = len(nums) - 2
    while inverse_pt >= 0 and nums[inverse_pt+1] <= nums[inverse_pt]:
        inverse_pt -= 1

    if inverse_pt < 0:
        nums = sorted(nums)
        print(nums) # [1,2,3]
        return

    # find a smallest elem that's bigger than inverse_pt
    for i in range(len(nums)-1, inverse_pt, -1):
        if nums[i] > nums[inverse_pt]:
            nums[i], nums[inverse_pt] = nums[inverse_pt], nums[i]
            break

    # sort what's after new elem at inverse_pt
    nums[inverse_pt+1:] = sorted(nums[inverse_pt+1:])

We can't tell why your straightforward attempts fail, because you didn't describe how you used your reversal and sorting attempts. — Prune, Jul 25 '19 at 17:08
In-place usually means no extra memory is required, not just that the result overwrites the original input. Here, `sorted` has to return a brand new list before its elements can be copied back into the exiting list `nums`. — chepner, Jul 25 '19 at 17:13
Thank y'all! @Stef, your answer enlightened me to see: nums is a reference to the list, not the list itself and this is the reason behind why nums = sorted(nums) does not actually modify in-place. — Schwinn Zhang, Jul 25 '19 at 21:57

score 0 · Answer 1 · answered Jul 25 '19 at 17:08

They don't sort in place because that's not how they're designed.

Slicing always creates a new list that has some subset of elements from the original list in some order.

The sorted() method doesn't sort the list, it returns a sorted version of the list:

sorted(iterable, /, *, key=None, reverse=False)
    Return a new list containing all items from the iterable in ascending order.
           ^^^^^^^^^^

Same with the reversed() method.

If you want to sort a list in-place, just do lst.sort():

sort(self, /, *, key=None, reverse=False)
    Stable sort *IN PLACE*.

In general, this plays into part of python's design philosophy. In general, a method will either mutate its object or return a new, mutated version of the object without changing it. There are a couple of notable exceptions, mostly list.pop() (which is important for data science reasons and can be considered as a shorthand for two sequential operations), but slicing and sorted() (and reversed()) follow this paradigm.

Why do slicing and sorted fail to reverse list in place?

1 Answers1