Python code returning "none"

  • Thread starter member 428835
  • Start date
  • Tags
    Code Python
In summary, the conversation discusses a code that is supposed to output the next lexicographic permutation given a list of integers, but instead returns None. The expert suggests looking at the reverse function and considering what value is expected to be returned. The solution is to either add a return statement in the reverse function or to create a new list inside the function and return that instead of mutating the original list. The conversation also mentions some typos in the original code that may have caused errors when running it.
  • #1
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!

Python:
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))
 
Technology news on Phys.org
  • #2
@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?)
 
  • Like
Likes member 428835 and FactChecker
  • #3
PeterDonis said:
@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!
 
  • #4
So, solution for anyone struggling with wondering why a function outputs None, a first attempt is making sure you include the return command...:headbang:
 
  • #5
joshmccraney said:
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.

joshmccraney said:
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.

joshmccraney said:
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:

Python:
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.
 
  • #6
PeterDonis said:
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:

Python:
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.
 
  • #7
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
 
  • #8
PeterDonis said:
@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'.
 
  • Like
Likes member 428835
  • #9
Mark44 said:
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.
 
  • #10
PeterDonis said:
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?
 
  • #11
Mark44 said:
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.
 
  • #12
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.
 
  • Like
Likes pbuk
  • #13
Yes @Ibix
Ibix said:
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).
Ibix said:
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.
 
  • #14
joshmccraney said:
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.
PeterDonis said:
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
Python:
    ob1.nextPermutation(nums)
    print(nums)

PeterDonis said:
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.

PeterDonis said:
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.
 
Last edited:
  • #15
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.
 
  • #16
pbuk said:
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.

pbuk said:
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.

pbuk said:
This would be very expensive.
Depends on how many elements are in the list and how many permutations need to be processed.
 
  • Like
Likes member 428835
  • #17
pbuk said:
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.

pbuk said:
If you are going to implement it as a class this way, nextPermutation should be implemented as a static method.
Same comment as above.

pbuk said:
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.

pbuk said:
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.
 
  • #18
PeterDonis said:
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.

PeterDonis said:
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.

PeterDonis said:
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).
 
  • Like
Likes member 428835
  • #19
pbuk said:
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.
 
  • Like
Likes member 428835
  • #20
PeterDonis said:
"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

PeterDonis said:
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.
 
Last edited:
  • #21
pbuk said:
Agreed.

pbuk said:
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.

pbuk said:
and a new number object for each entry in the list.
No. Cloning a list doesn't copy the objects:

Python:
>>> 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:

Code:
>>> 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
 
  • #22
PeterDonis said:
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).

PeterDonis said:
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.
 
  • #23
PeterDonis said:
No. Cloning a list doesn't copy the objects:
It does if they are primitives as they are here.
 
  • #24
pbuk said:
Good grief, so there is.
Yes, I was surprised too when I realized that option wasn't Python 3.
 
  • #25
pbuk said:
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.
 
  • #26
PeterDonis said:
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.
 
  • #27
pbuk said:
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.

pbuk said:
* 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).
 
  • Like
Likes pbuk
  • #28
pbuk said:
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.
 
  • Like
Likes pbuk
  • #29
PeterDonis said:
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:
Python:
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))

Code:
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
 
  • #30
pbuk said:
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.

pbuk said:
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.
 
  • Like
Likes pbuk
  • #31
PeterDonis said:
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.
 
  • #32
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.

pbuk said:
 
  • #33
pbuk said:
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.
 
  • #34
PeterDonis said:
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.

PeterDonis said:
The relevant function name in the OP is nextPermutation.
No, the relevant function name is reverse:
pbuk said:
joshmccraney said:
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.

PeterDonis said:
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.
 
  • #35
pbuk said:
No, the relevant function name is reverse:
Ah, yes, that's right. That one I agree would be naturally interpreted as mutating in place.

pbuk said:
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.

pbuk said:
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.
 
  • Like
Likes pbuk

1. Why does my Python code return "None"?

Python code will return "None" when there is no explicit return statement in the code. This means that the function or statement being executed does not have a specific value to return, so it defaults to "None".

2. How do I fix my Python code from returning "None"?

To fix this issue, you can add a return statement with a value or variable that you want the code to return. This will ensure that the code does not default to "None".

3. Can "None" be used as a valid value in Python?

Yes, "None" is a valid value in Python and is commonly used to indicate the absence of a value or to represent a null value.

4. Why does my Python code return "None" even though I have a return statement?

This could be due to the code not reaching the return statement, either because of a conditional statement or an error that occurs before the return statement is executed. It is important to check the flow of the code to ensure that the return statement is being reached.

5. Is there a difference between "None" and "NoneType" in Python?

"None" and "NoneType" are used interchangeably in Python and both represent the same null value. However, "NoneType" is the actual data type of "None" in Python.

Similar threads

  • Programming and Computer Science
Replies
22
Views
704
  • Programming and Computer Science
Replies
4
Views
969
  • Programming and Computer Science
Replies
6
Views
1K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
2
Replies
43
Views
3K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
2
Views
2K
Back
Top