Python list permutations in lexicographic order

Question

This code is about Lexicographic Ordering algorithms and its works but how can I change the style of the code to professional coding style?

from typing import List 
def swap(_list: List, index1: int, index2: int):
 _list[index1], _list[index2] = _list[index2], _list[index1]
 return _list
 
def lexico_graphic(items: List):
 paths = [items]
 while True:
 # step 1
 largest_i = None
 for i in range(len(items) - 1):
 if items[i] < items[i + 1]:
 largest_i = i
 if largest_i is None:
 return paths
 # step 2
 largest_j = 0
 for j in range(len(items)):
 if items[largest_i] < items[j]:
 largest_j = j
 # step 3
 items = swap(items, largest_i, largest_j)
 # step 4
 items = items[:largest_i + 1] + items[:largest_i:-1]
 paths.append(items)

• coderodde: What version of Python do you use?
• coderodde: For me, the token ‘items: List’ causes compile-time error.

Answer 1

In Python objects are passed into functions by creating a reference that points to the same value, meaning that when you invoke your function swap() on list items, local _list refers to the exact same items object you passed in there. When you mutate _list in the next line (_list[index1], _list[index2] = _list[index2], _list[index1]) the underlying object changes, which means your function is no longer pure: you were trying to return a new list with 2 items swapped, but instead modified the original list.

If you don't want this function to mutate the original list you can write it like this:

def swap(_list: List, index1: int, index2: int):
 new_list = _list[:] # equivalent to `_list.copy()`
 new_list[index1], new_list[index2] = new_list[index2], new_list[index1]
 return new_list

As you can see the original list never changes.

If you instead wanted the function to mutate your list, you can get rid of the return statement:

def swap(_list: List, index1: int, index2: int):
 _list[index1], _list[index2] = _list[index2], _list[index1]

and use it without the assignment:

swap(items, largest_i, largest_j)
# instead of
items = swap(items, largest_i, largest_j)

---

The algorithm looks fine, but naming may need some adjustments:
_list - underscores in python are used as access modifiers, this parameter can be named items for example
lexico_graphic - it's unclear what this function does by looking at its name