Python code returning "none"

[member 428835]

Hi PF!

I'm trying to write a code that, given a list of integers, will output the next lexicographic permutation. But my output gives me None, and I can't see why. Is it because I am incorrectly calling the reverse function? Any help is greatly appreciated!

class Solution(object):
    def reverse(self, nums, i, j):
        while i < j:
            nums[I], nums[j] = nums[j], nums
            i += 1
            j -= 1

    def nextPermutation(self, nums):
        # Length of the array
        n = len(nums)
        # Index of the first element that is smaller than
        # the element to its right.
        index = -1
        # Loop from right to left
        for i in range(n - 1, 0, -1):
            if nums[I] > nums[i - 1]:
                index = i - 1
                break
        # Base condition
        if index == -1:
            return self.reverse(nums, 0, n - 1)
        j = n - 1
        # Scan right to left to find first element
        # greater than the above find element
        for i in range(n - 1, index, -1):
            if nums[I] > nums[index]:
                j = i
                break
        # Swap the elements
        nums[index], nums[j] = nums[j], nums[index]
        # Reverse the elements from index + 1 to the nums.length
        newNum = self.reverse(nums, index + 1, n - 1)
        return newNum
if __name__ == "__main__":
    nums = [1,3,2]
    ob1 = Solution()
    print(ob1.nextPermutation(nums))

 

[PeterDonis]

@joshmccraney your code has typos in it and raises NameError when it is run. Have you actually tried to run the exact code you posted? I'm guessing not. You should always cut and paste the exact code you have actually run, not try to re-type something.

With the typos fixed, your code does indeed return None. I suggest you look carefully at your reverse function and ask yourself what value you would expect it to return to be put in newNum in line 32 of your code. (Hint: is there any return statement in the reverse function?)

 

[member 428835]

@joshmccraney your code has typos in it and raises NameError when it is run. Have you actually tried to run the exact code you posted? I'm guessing not. You should always cut and paste the exact code you have actually run, not try to re-type something.

With the typos fixed, your code does indeed return None. I suggest you look carefully at your reverse function and ask yourself what value you would expect it to return to be put in newNum in line 32 of your code. (Hint: is there any return statement in the reverse function?)

I was thinking that function would change the nums variable. Guess I need to try return nums? But I did run that code verbatim as posted and it outputs None; I'm not getting an error.

Edit: all I changed was adding the return nums in the reverse function and it works. Thanks for bringing this to my attention! I appreciate it!

 

[member 428835]

So, solution for anyone struggling with wondering why a function outputs None, a first attempt is making sure you include the return command...

 

[PeterDonis]

I was thinking that function would change the nums variable.

It does, but that doesn't help because of the way line 32 of your code is written.

Guess I need to try return nums?

That would be one possible fix. The other would be to let the reverse function mutate nums in place and just have line 32 call it without assigning any return value. Then your nextPermutation function could just return nums after reverse mutates it.

The first option is probably better programming practice; but if you're going to do that, it's better to create a new list inside the reverse function and return that, instead of mutating nums in place and then returning it.

I did run that code verbatim as posted

You couldn't have; you have capital I's in the code you posted but no capital I is ever assigned a value so there is no such variable in any namespace. That's why NameError gets thrown. Here's what I get running exactly what you posted, at a bash shell on Linux:

Traceback (most recent call last):
  File "mcraney.py", line 37, in <module>
    print(ob1.nextPermutation(nums))
  File "mcraney.py", line 16, in nextPermutation
    if nums[I] > nums[i - 1]:
NameError: name 'I' is not defined

Unless you're running this code in some kind of IDE or other environment that silently corrects the case of your variables, this is the output you should get.

 

[member 428835]

It does, but that doesn't help because of the way line 32 of your code is written.That would be one possible fix. The other would be to let the reverse function mutate nums in place and just have line 32 call it without assigning any return value. Then your nextPermutation function could just return nums after reverse mutates it.

The first option is probably better programming practice; but if you're going to do that, it's better to create a new list inside the reverse function and return that, instead of mutating nums in place and then returning it.You couldn't have; you have capital I's in the code you posted but no capital I is ever assigned a value so there is no such variable in any namespace. That's why NameError gets thrown. Here's what I get running exactly what you posted, at a bash shell on Linux:

Traceback (most recent call last):
  File "mcraney.py", line 37, in <module>
    print(ob1.nextPermutation(nums))
  File "mcraney.py", line 16, in nextPermutation
    if nums[I] > nums[i - 1]:
NameError: name 'I' is not defined

Unless you're running this code in some kind of IDE or other environment that silently corrects the case of your variables, this is the output you should get.

Okay, I did see a few of these randomly show up after I copy-pasted, and was wondering how they got there. Thought I deleted em all. I think it had something to do with me hitting the "preview" option over and over again, but I could be wrong. So no clue how they got there, but thanks for the feedback.

 

[member 428835]

And weird, now that I look, it appears some of the i's were capitalized in the code. Like something changed the lowercase to capital. Because when I ran my code adding the return nums statement, everything worked. The mystery of why this happened eludes me

 

[Mark44]

@joshmccraney your code has typos in it

The typos I saw are an artifact of browsers attempting to convert bracketed 'i' characters into BBCode for italics. The workaround if you have array indexes named 'i' is to leave a space between the left bracket and 'i'. Another is to use a different index variable, like 'j'.

 

[PeterDonis]

The typos I saw are an artifact of browsers attempting to convert bracketed 'i' characters into BBCode for italics.

It wouldn't just be the browser, it would be whatever javascript is running to translate things in the edit box. I wonder if it would be possible to disable the translation inside a code block. I'll post a separate request about that in the feedback forum.

 

[Mark44]

It wouldn't just be the browser, it would be whatever javascript is running to translate things in the edit box.

I don't know which software does exactly what, but possibly MathJax?

 

[PeterDonis]

I don't know which software does exactly what, but possibly MathJax?

Maybe, or possibly some other Javascript that tries to normalize and correct BBCode. I've had weird things happen sometimes when editing a post, when it thinks I've entered one half of a BBCode tag and it automatically inserts what it thinks is the other half, and I've had to go back and re-edit posts.

 

[Ibix]

I don't know, but I would guess that @joshmccraney had the editor in Rich Text mode, entered python without CODE tags, previewed it, noticed the missing CODE tags and edited them in, and previewed it again. The first preview interprets the i in square brackets as a BBCODE italic tag and swallows it, displaying italic text even when you return to the editor. Adding the CODE tags converts it back to a BBCODE tag on the second preview, but does so in capitals because BBCODE is case insensitive so it's presumably forgotten the tag's original case.

I don't think this is an issue if you remember the CODE tags before the first preview or use the editor in BBCODE mode.

 

[pbuk]

Yes @Ibix

I don't know

You are right, this is exacty what is happening and is expected behavior; this is how BBCode implements italic text (and B for bold, S for strikeout).

I don't think this is an issue if you remember the CODE tags before the first preview.

Or insert the code using the </> button in WYSIWYG mode. In general: use the buttons in WYSIWYG mode and type (all the right) tags in BBCode mode.

 

[pbuk]

Edit: all I changed was adding the return nums in the reverse function and it works.

Yes but that was the wrong thing to fix, read on.

That would be one possible fix. The other would be to let the reverse function mutate nums in place and just have line 32 call it without assigning any return value.

Then your nextPermutation function could just return nums after reverse mutates it.

There's no need to return anything from nextPermutation as it mutates the list argument in place. It should be called as

    ob1.nextPermutation(nums)
    print(nums)

The first option is probably better programming practice;

Not really. I have posted before about how side effects are undesireable, however for utility functions like this mutating the original list is not a side effect, it is the only thing the function does. Compare with Python's list.reverse() and list.sort() methods which also mutate in place.

but if you're going to do that, it's better to create a new list inside the reverse function and return that, instead of mutating nums in place and then returning it.

This would be very expensive.

 

[pbuk]

There are other issues with this implementation:

• The way you have implemented it there is no point in using a class: nextPermutation can be a simple function.
• If you are going to implement it as a class this way, nextPermutation should be implemented as a static method.
• Your class declaration should simply be class Solution:, you should not explicitly extend the object object.

Note that there is a built in function for lexicogrphic permutions.

 

[PeterDonis]

that was the wrong thing to fix

"Wrong" is rather a strong claim. If code works, it works. It might not be optimal in your opinion, but that doesn't make it wrong.

for utility functions like this mutating the original list is not a side effect

That depends on whether the original list might be used for something else. In this particular case it probably doesn't matter, but in general it might.

This would be very expensive.

Depends on how many elements are in the list and how many permutations need to be processed.

 

[PeterDonis]

The way you have implemented it there is no point in using a class: nextPermutation can be a simple function.

I suspect this code is taken from a submission to a LeetCode question or something similar. Those require your code to be structured in this way, with a Solution class and the function that does the actual work as a method on it. Kind of weird, but that's the way they do it.

If you are going to implement it as a class this way, nextPermutation should be implemented as a static method.

Same comment as above.

Your class declaration should simply be class Solution:, you should not explicitly extend the object object.

This is valid, but so is doing it the OP's way. I believe the LeetCode site automatically formats the skeleton Python code it gives you the way the OP's code is formatted. That way is not wrong, even if it doesn't meet your personal preferences.

Note that there is a built in function for lexicographic permutions.

Sometimes people choose to implement things themselves so they can see how they work.

Also, the built-in function does not give you any way to start at a chosen permutation and get the next one, it just iterates through all of them from start to finish. So using it would mean you'd have to iterate through the permutations the built-in returns until you find the one that matches the one you were given, and then return the next one. That might well be slower than figuring out the next permutation directly.

 

[pbuk]

I suspect this code is taken from a submission to a LeetCode question or something similar. Those require your code to be structured in this way, with a Solution class and the function that does the actual work as a method on it. Kind of weird, but that's the way they do it.
...
Same comment as above.

Good point: https://leetcode.com/problems/permutations/ for example.

This is valid, but so is doing it the OP's way. I believe the LeetCode site automatically formats the skeleton Python code it gives you the way the OP's code is formatted. That way is not wrong, even if it doesn't meet your personal preferences.

It's not just a personal preference, class Solution(object) is an irrelevant hangover from Python 2 and has no place in code written in 2022. It is not the way leetcode presents it in the link above.

Sometimes people choose to implement things themselves so they can see how they work.

Also, the built-in function does not give you any way to start at a chosen permutation and get the next one, it just iterates through all of them from start to finish. So using it would mean you'd have to iterate through the permutations the built-in returns until you find the one that matches the one you were given, and then return the next one. That might well be slower than figuring out the next permutation directly.

Agreed; I simply wanted to make the OP aware of the built-in (and the concept of iterators in Python generally which is an important one).

 

[PeterDonis]

It is not the way leetcode presents it in the link above.

Yes, you're right, if you select "Python3" it just has class Solution:. There is still a "Python" option on Leetcode, which does have class Solution(object):; I think the last time I did a Leetcode problem I didn't realize there were two Python options and just picked the first one.

 

[pbuk]

"Wrong" is rather a strong claim. If code works, it works. It might not be optimal in your opinion, but that doesn't make it wrong.

Agreed.

Edit: but see the same considerations in relation to list.sort: https://docs.python.org/3/faq/design.html#why-doesn-t-list-sort-return-the-sorted-list

Depends on how many elements are in the list and how many permutations need to be processed.

Cloning a list of numbers is always an expensive operation in Python requiring the creation of a new object for the list and a new number object for each entry in the list. Reordering elements is just swapping pointers.

 

[PeterDonis]

Agreed.

Cloning a list of numbers is always an expensive operation in Python requiring the creation of a new object for the list

Yes, but whether that is "expensive" is relative. For many programs it's too cheap to worry about.

and a new number object for each entry in the list.

No. Cloning a list doesn't copy the objects:

>>> l1 = [1, 2, 3]
>>> l2 = list(l1)
>>> l2 is l1
False
>>> all(l2[i] is l1[i] for i in range(len(l1)))
True

Even for lists containing mutable objects, you need copy.deepcopy if you want the objects copied as well:

>>> l1 = [['a'], ['b'], ['c']]
>>> l2 = list(l1)
>>> l2 is l1
False
>>> all(l2[i] is l1[i] for i in range(len(l1)))
True
>>> import copy
>>> l3 = copy.copy(l1)
>>> all(l3[i] is l1[i] for i in range(len(l1)))
True
>>> l4 = copy.deepcopy(l1)
>>> all(l4[i] is l1[i] for i in range(len(l1)))
False

 

[pbuk]

Yes, you're right, if you select "Python3" it just has class Solution:.

Ah, Python3 was already selected for me (must have been a cookie).

There is still a "Python" option on Leetcode, which does have class Solution(object):; I think the last time I did a Leetcode problem I didn't realize there were two Python options and just picked the first one.

Good grief, so there is. Python 2 reached end of life over two years ago and if they are going to retain it as an option it should be hidden away somewhere and called Python 2. In 2022 Python means Python 3.

 

[pbuk]

No. Cloning a list doesn't copy the objects:

It does if they are primitives as they are here.

 

[PeterDonis]

Good grief, so there is.

Yes, I was surprised too when I realized that option wasn't Python 3.

 

[PeterDonis]

It does if they are primitives.

Please post an explicit interactive session showing the case you are talking about. I have posted two interactive sessions showing what it actually takes to get Python to clone the elements of a list as well as the list itself, namely, copy.deepcopy. I am not aware of any other way of doing it.

 

[pbuk]

Please post an explicit interactive session showing the case you are talking about.

It won't show up in an interactive session, I am not talking about userspace objects or copy vs deepcopy (which does not in fact create a new object for a primitive) and I should have used a different word. Let me rephrase my assertion:

Cloning a list is always an expensive operation in Python requiring the creation of a new object for the cloned list and a new entry on the internal linked list of pointers* for each entry in the list, creating (n+1) new entries on the internal heap. Reordering elements is just swapping pointer values in existing internal heap entries.

* or integers or certain other special optimization cases in CPython.

 

[PeterDonis]

Cloning a list is always an expensive operation in Python requiring the creation of a new object for the cloned list and a new entry on the internal linked list of pointers* for each entry in the list, creating (n+1) new entries on the internal heap.

Ah, ok, now I see what you mean. But this is true regardless of what kinds of objects the list is storing, so I don't see the point of your statement that "it does if they are primitives". What you're describing here gets done every time a list is cloned, whether the list is storing "primitives" or not.

* or integers or certain other special optimization cases in CPython.

Do you mean integers small enough that they are pre-created by the interpreter (similar to singletons like None)?

As I understand the internal C code for the list object, none of that affects how the list stores pointers internally. The list [None, None, None, None, None] still has to have five entries in its internal linked list of pointers, even though every entry's pointer is identical (they all point to the interpreter's pre-generated None object).

 

[PeterDonis]

a new entry on the internal linked list of pointers

Thinking this over, I'm not sure it's true; I thought CPython lists were allocated as arrays of pointers (with the array size being extended if needed when the list is appended to). I'll have to take a look at the CPython source code when I get a chance.

 

[pbuk]

Thinking this over, I'm not sure it's true; I thought CPython lists were allocated as arrays of pointers (with the array size being extended if needed when the list is appended to). I'll have to take a look at the CPython source code when I get a chance.

Oops, you are absolutely right: https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython. It's still O(n) but with a pretty small constant.

Anyway you asked for an interactive session; I'll give you a script instead:

from copy import copy, deepcopy

compound = [0]
original = [1, 1.0, 'Hello', True, compound]
copyList = copy(original)
deepCopyList = deepcopy(original)

compound[0] = 1

comments = ([
    'Integers are a special case and are never deep copied',
    'Floats are never deep copied',
    'Strings are never deep copied',
    'Booleans are a REALLY special case and are never deep copied',
    'Only compound objects are deep copied',
])
for i in range(len(original)):
    print(comments[i])
    print(original[i], copyList[i], deepCopyList[i])
    print(id(original[i]), id(copyList[i]), id(deepCopyList[i]), '\n')

print('Booleans are a REALLY special case: see how anything with the')
print('value True always points to the same memory location!', id(True))

Integers are a special case and are never deep copied
1 1 1
140714672596784 140714672596784 140714672596784 

Floats are never deep copied
1.0 1.0 1.0
2049093583344 2049093583344 2049093583344 

Strings are never deep copied
Hello Hello Hello
2049093700400 2049093700400 2049093700400 

Booleans are a REALLY special case and are never deep copied
True True True
140714672314192 140714672314192 140714672314192 

Only compound objects are deep copied
[1] [1] [0]
2049094088576 2049094088576 2049093240384 

Booleans are a REALLY special case: see how anything with the
value True always points to the same memory location! 140714672314192

 

[PeterDonis]

Oops, you are absolutely right: https://docs.python.org/3/faq/design.html#how-are-lists-implemented-in-cpython.

Yes, the relevant C structure definition is here:

https://github.com/python/cpython/blob/main/Include/cpython/listobject.h

The ob_item field points to a vector of pointers to PyObjects.

you asked for an interactive session, here is an interesting one

Yes, immutable objects in general are not cloned even in a deep copy. There would be no point. Only mutable objects are.

The booleans are a "really special case" because they are among the objects pre-created by the interpreter, like None and sufficiently small integers (256 or less, IIRC). So they are effectively singletons and there will never be more than one of them.

 

[willem2]

Please post an explicit interactive session showing the case you are talking about. I have posted two interactive sessions showing what it actually takes to get Python to clone the elements of a list as well as the list itself, namely, copy.deepcopy. I am not aware of any other way of doing it.

For short lists, making copies isn't very inefficient, but you really shouldn't use deepcopy() if you don't have to.

720.000 iterations of nextpermutation(), starting with [1,2,3,4,5,6] took:
0.84s with the reverse function modifiying the list, and not returning anything from reverse()
0.91s with making a copy of the list with newlist = list[::]
1.06s using copy.copy() to make a copy of the list
3.81s using copy.deepcopy().
deepcopy still needs to examine all the objects in the list to see if any of them are lists , even if the result is the same as copy() for a list of numbers.

 

[pbuk]

But the point is not really about cost, it is about the Principle of Least Astonishment.

If you have a function doSomethingToAList(list, moreArgs...) that does not return anything (or returns, say, an integer giving the number of entries that were affected) then it is clear that if it is going to work at all then it must mutate the list argument. You therefore know that if you don't want your list to be mutated you need to copy (or deepcopy) it first.

On the other hand you would expect a function extractMaximumValuesFrom(list, count) to return a new list with no more than [count] entries; you would NOT expect it to mutate the list argument.

see the same considerations in relation to list.sort: https://docs.python.org/3/faq/design.html#why-doesn-t-list-sort-return-the-sorted-list

 

[PeterDonis]

If you have a function doSomethingToAList(list, moreArgs...) that does not return anything (or returns, say, an integer giving the number of entries that were affected) then it is clear that if it is going to work at all then it must mutate the list argument. You therefore know that if you don't want your list to be mutated you need to copy (or deepcopy) it first.

On the other hand you would expect a function extractMaximumValuesFrom(list, count) to return a new list with no more than [count] entries; you would NOT expect it to mutate the list argument.

This assumes that knowing which option is the "least astonishment" option for a given function name is a simple thing. Is it?

The relevant function name in the OP is nextPermutation. Just looking at the name, would you expect this to mutate the list in place? Or would you expect it to return a new list containing the next permutation? I would expect the latter, but you were arguing earlier in the thread that this function should not return a value but should mutate the list in place, which seems to indicate that you would expect the former.

 

[pbuk]

This assumes that knowing which option is the "least astonishment" option for a given function name is a simple thing. Is it?

Well-chosen names can help this.

The relevant function name in the OP is nextPermutation.

No, the relevant function name is reverse:

Edit: all I changed was adding the return nums in the reverse function and it works. Thanks for bringing this to my attention! I appreciate it!

Yes but that was the wrong thing to fix, read on.

As this is a verb I would expect it to do something. It would be better named reversePart because that is what it does (and to avoid confusion with a list object's reverse method). A function that returned a part-reversed list would be better named getPartReversed.

you were arguing earlier in the thread that this function should not return a value but should mutate the list in place

The point I was trying to make was that a function should not both mutate a list and return the mutated list; it should either mutate the list or return a new list. As a secondary point, I was arguing that in this case there was no advantage in returning a new list so I would choose mutation with a void return value.

 

[PeterDonis]

No, the relevant function name is reverse:

Ah, yes, that's right. That one I agree would be naturally interpreted as mutating in place.

The point I was trying to make was that a function should not both mutate a list and return the mutated list; it should either mutate the list or return a new list.

Yes, agreed.

As a secondary point, I was arguing that in this case there was no advantage in returning a new list so I would choose mutation with a void return value.

For this particular problem, since it's only asking for the next permutation, I agree it's simpler just to mutate in place. I always tend to think in more general terms, and I can think of plenty of reasons why it would be better to return a new list in a more general purpose program. But there might also be reasons in other particular use cases to mutate in place instead.