Steinhaus-Johnson-Trotter Algorithm

Question

I began to program a little while ago and tried to implement my first algorithm: the Steinhaus-Johnson-Trotter algorithm. This algorithm generates a sequence of permutations of \$n\$ elements such that each permutation differs from the previous permutation by an exchange of two adjacent elements. This sequence of permutations is different from the one generated by itertools.permutations in the standard library (which is in lexicographic order).

I'm sure that it isn't the most efficient way. But as I looked for the other solutions I got confused due to the used programming syntax and the recursive functions, so I await your improvement suggestions.

I commented as much as needed and hopefully this will help you to understand it faster.

from sys import exit
def makeList():
 # Just makes a list in an ascending order
 # The ascending order is important!
 # The initial direction is 0 (LEFT)
 LIST = []
 try:
 n = int(input("How many elements?\n> "))
 for i in range(1,n+1):
 LIST.append([i,0])
 getAllPermutations(LIST)
 except ValueError as e:
 print("Value Error : ", e)
 sys.exit(0)
def changeDirections(LIST, MI):
 # self explanatory
 for element in LIST:
 if element[0] > LIST[MI][0]:
 if element[1] == 0:
 element[1] = 1
 elif element[1] == 1:
 element[1] = 0
def swap(LIST, MI):
 # Just swaps the MI with adjacent item based on the MI's direction
 if LIST[MI][1] == 0:
 tempElement = LIST[MI-1]
 LIST[MI-1] = LIST[MI]
 LIST[MI] = tempElement
 elif LIST[MI][1] == 1:
 tempElement = LIST[MI+1]
 LIST[MI+1] = LIST[MI]
 LIST[MI] = tempElement
def findLargestMI(LIST):
 # 0 < -- LEFT
 # 1 > -- RIGHT
 MI = None
 foundMI = False
 for i in LIST:
 # True if the direction of i is left
 if i[1] == 0:
 # If it isn't the first element in the list keep going
 # That's because if the list looks like this <3 <1 <2
 # <3 can't be a Mobile Integer thus it doesn't need
 # to be checked
 if LIST.index(i) != 0:
 # If it's the first iteration than currentMI is None
 # that's why i wrote an if-statement
 if MI == None:
 # If the current iteration element is bigger than
 # the neighbor right of it than declare it as
 # the current Mobile Integer
 if i[0] > LIST[LIST.index(i) - 1][0]:
 MI = LIST.index(i)
 foundMI = True
 elif MI != None:
 # Is the current iteration element bigger than
 # its neighbor
 # and is it bigger than the current Mobile
 # Integer?
 if ( i[0] > LIST[LIST.index(i) - 1][0] ) and ( i[0] > LIST[MI][0] ):
 MI = LIST.index(i)
 foundMI = True
 # True if the direction of i is right
 if i[1] == 1:
 # Every following step is the reverse of the code above
 if LIST.index(i) != LIST.index(LIST[-1]):
 if MI == None:
 if i[0] > LIST[LIST.index(i) + 1][0]:
 MI = LIST.index(i)
 foundMI = True
 elif MI != None:
 if ( i[0] > LIST[LIST.index(i) + 1][0]) and ( i[0] > LIST[MI][0]):
 MI = LIST.index(i)
 foundMI = True
 if not foundMI:
 # If it's false then there isn't anymore Mobile Integer
 return foundMI
 return MI
def getAllPermutations(LIST):
 # The reason why i change the directions before the swapping
 # is that when i swap the items before the change of directions
 # an other element gets in the place of the Mobile Integer and
 # wrong elements are changed in direction. Further it
 # doesn't affect the procedure
 #LIST.sort(key=lambda x: x[0])
 index = 1
 while True:
 printListWithDirections(LIST, index)
 index += 1
 MI = findLargestMI(LIST)
 if isinstance(MI, bool) and MI == False:
 print("#####END#####")
 break;
 changeDirections(LIST, MI)
 swap(LIST, MI)
def printListWithDirections(LIST, index):
 output = ""
 secondPrint = False
 for i in LIST:
 # Nothing important. I just want the list to be shown
 # in a pretty way for some reason
 if secondPrint:
 output += (" ")
 else:
 secondPrint = True
 if i[1] == 0:
 output += ("<" + str(i[0]))
 elif i[1] == 1:
 output += (str(i[0]) + ">")
 print(str(index)+ ". " + output)
if __name__ == '__main__':
 makeList()

• 301_Moved_Permanently: What would help understand it faster is a description of what the algorithm is supposed to achieve.
• Onur C.Y.: Yes, of course. The algorithm is supposed to give all possible permutations of n elements.

Answer 1

There are no unit tests. It would be helpful to compare your results with what the library permutations routine produces.

 makeList()

Pep 8 asks that you spell this make_list(), and similarly for your other functions. Please run flake8 and follow its warnings.

 LIST = []

This is not a manifest constant. Please spell it list_ (or lst). Similarly for mi.

# self explanatory

Delete.

The comments:

 # The initial direction is 0 (LEFT)

and:

 # True if the direction of i is left

suggest putting LEFT / RIGHT in an Enum.

 # If it's the first iteration than currentMI is None
 # that's why i wrote an if-statement
 if MI == None:

The natural way to express that would be to loop with for n, i in enumerate(LIST):, and then to test if n == 0:. I'm just reading your English sentence and writing the corresponding code.

 if secondPrint:
 output += (" ")
 else:
 secondPrint = True

There's no need for that. Define output = [], and use output.append('<%d' % i[0]) or output.append('%d>' % i[1]). Then at the end ' '.join(output) will give the desired result.

 tempElement = LIST[MI-1]
 LIST[MI-1] = LIST[MI]
 LIST[MI] = tempElement

The conventional way to express that in python is:

 LIST[MI-1], LIST[MI] = LIST[MI], LIST[MI-1]

You should cite your reference. For example, if you are following https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm then say so, and use identifiers like pi that the reference uses. You're apparently using another reference, given your use of "mobile integer".

Your prose helpfully explains that this is the Steinhaus-Johnson-Trotter algorithm. But that appears nowhere in your identifiers or comments. Please add it.

• Onur C.Y.: Thank you for the constructive answer! I used following source : cut-the-knot.org/Curriculum/Combinatorics/JohnsonTrotter.shtml

Answer 2

1. Review

1. In the Python world, we generally format our code according to "PEP 8 — Style Guide for Python Code. This isn't compulsory (your programs will work fine if you use some other style) but if you follow it then you'll find it easier to collaborate with other Python programmers, because they will find it easier to read and edit your code, and vice versa.

   In my answer below I'm going to rewrite the code using the PEP8 conventions as I go along, for example changeDirections will become _change_directions and LIST will becomes permutation and so on. I won't go into detail about each change to the names; take a look at PEP8 and you'll see why I made each change.

2. The code uses 0 to mean "moving left" and 1 to mean "moving right". This is hard for people reading the code to remember—it might have made equal sense to use 0 for "moving right" and 1 for "moving left". It would make the code clearer if you gave names to these values, for example, you could have global variables:

   _LEFT = 0
   _RIGHT = 1
   

   But actually it might be more convenient to use this representation:

   _LEFT = -1
   _RIGHT = 1
   

   This would allow you to simplify changeDirections and swap and findLargestMI. I'll show how this works later.

3. The code represents the state of each element of the permutation using a list of length two, where the first item in the list is the element, and the second item indicates which direction it is moving, so for example LIST[MI][1] is the direction in which the element at position MI in the permutation is moving. Again, this is hard for people reading the code to remember—it would have made equal sense to represent the state the other way round, so that LIST[MI][1] is the element and LIST[MI][0] the direction.

   To make the code clearer, we can represent the state of an element of the permutation using an object with two attributes (rather than a list with two items). We can implement this by writing a class:

   _LEFT = -1
   _RIGHT = 1
   class PermutationElement:
    "Element of a permutation, with current direction."
    def __init__(self, element, direction):
    assert direction in (_LEFT, _RIGHT)
    self.element = element
    self.direction = direction
   

   Using this class requires some adjustments to the other functions, which we'll see as we go along.

4. The function makeList does three things: (i) it prompts the interactive user for the number of elements in the list; (ii) builds the initial state of the permutation; (iii) calls getAllPermutations.

   This makes it hard to use these permutations from another piece of code, for example if you wanted to write automatic tests. The problem is that there would need to be an interactive user present to respond to the prompt.

   It would be better to rearrange the code so that (ii) was moved to the start of getAllPermutations, like this:

   def print_permutations(iterable):
    "Print the permutations of an iterable in plain changes order."
    # Build initial state, with all elements moving left.
    LIST = [PermutationElement(element, _LEFT) for element in iterable]
    # ... continue as before ...
   

   We can now rewrite the top-level code like this:

   if __name__ == '__main__':
    n = int(input("How many elements? "))
    print_permutations(range(1, n + 1))
   

   Note that there is no need to catch the ValueError from the call to int and then exit the program — the program will exit anyway.

5. Now we can simplify changeDirections like this:

   def _change_directions(permutation, mobile):
    "Reverse direction of elements in permutation larger than mobile element."
    mobile_element = permutation[mobile].element
    for e in permutation:
    if e.element > mobile_element:
    e.direction *= -1
   

   Notice that permutation[mobile].element does not change during the execution of this function, so we can remember its value in a local variable and avoid re-computing it.

6. We can also simplify swap like this, using the direction to compute the new position of the mobile element, and using tuple assignment to avoid the need for tempElement:

   def _swap(permutation, i):
    "Update permutation by moving the i'th element in its direction."
    j = i + permutation[i].direction
    assert 0 <= j < len(permutation)
    permutation[i], permutation[j] = permutation[j], permutation[i]
   

   Notice the assertion checking that the new position of the mobile element is within the bounds of the array. Assertions like this help us check that we've implemented an algorithm correctly.

7. In printListWithDirections there is some complicated logic involving the flag secondPrint in order to get the spacing right. But this is unnecessary: if you removed the extra space from the line

   print(str(index)+ ". " + output)
   

   then there would be no need for the flag.

8. Instead of constructing a string in memory from some substrings, and then printing it in one go, why not print each of the substrings as you go along? Like this:

   def _print_permutation(permutation, n):
    "Print the nth permutation, with directions for the elements."
    print("{}.".format(n), end="")
    for e in permutation:
    if e.direction == _LEFT:
    print(" <{}".format(e.element), end="")
    else:
    print(" {}>".format(e.element), end="")
    print("")
   

9. This would be even simpler with a lookup table to find the format string corresponding to a direction:

   # Mapping from direction to corresponding format string.
   _FORMAT = {_LEFT: " <{}", _RIGHT: " {}>"}
   def _print_permutation(permutation, n):
    "Print the nth permutation, with directions for the elements."
    print("{}.".format(n), end="")
    for e in permutation:
    print(_FORMAT[e.direction].format(e.element), end="")
    print("")
   

10. Now we come to the function findLargestMI. This makes a lot of use of LIST.index to find the position of a element in the permutation, for example here the code checks whether i is the first element in the permutation:

    if LIST.index(i) != 0:
    

    But LIST.index is an expensive operation: it takes time proportional to the length of LIST. It is best to avoid this if there is some other means of knowing the position of an element in a list. In this case you know the index of element i because you got hold of it by iterating over the list:

    for i in LIST:
    

    and Python provides the enumerate function for iterating over the elements of a list and their indexes. So you could write:

    for index, i in enumerate(LIST):
    

    and use index instead of LIST.index(i).

11. Normally in Python we use the name i for an index, and another name, for example element or item, for the elements of a list. So I will be using:

    for i, e in enumerate(permutation):
    

    where i is the index and e is the element of the permutation.

12. When there are two if tests in succession, like this:

    if i[1] == 0:
     if LIST.index(i) != 0:
     # body
    

    It often makes sense to combine them using and, saving a level of indentation for the body:

    if i[1] == 0 and LIST.index(i) != 0:
     # body
    

    In my version of the code this becomes:

    if e.direction == _LEFT and i != 0:
    

13. Consider this block of code:

     if MI == None:
     if i[0] > LIST[LIST.index(i) - 1][0]:
     MI = LIST.index(i)
     foundMI = True
     elif MI != None:
     if ( i[0] > LIST[LIST.index(i) - 1][0] ) and ( i[0] > LIST[MI][0] ):
     MI = LIST.index(i)
     foundMI = True
    

    The conditions on the consecutive if statements can be joined with and as discussed above, producing (in my version of the code):

    if mobile is None and e.element > permutation[i - 1].element:
     mobile = i
     found_mobile = True
    elif (mobile is not None and e.element > permutation[i - 1].element
     and e.element > permutation[mobile].element):
     mobile = i
     found_mobile = True
    

    You'll see that the bodies of the two conditions are identical, so we can combine the two conditions into one:

    if (e.element > permutation[i - 1].element
     and (mobile is None or e.element > permutation[mobile].element)):
     mobile = i
     found_mobile = True
    

14. The variable found_mobile is not needed because its value is always the same as that of the expression mobile is None.

15. Repeating this exercise of combining adjacent conditions and simplifying, we can eventually reduce the function to this:

    def _find_mobile(permutation):
     """Return the index of the mobile element in the permutation, or None
     if there is no mobile element.
     """
     mobile = None
     for i, e in enumerate(permutation):
     j = i + e.direction
     if (0 <= j < len(permutation)
     and e.element > permutation[j].element
     and (mobile is None or e.element > permutation[mobile].element)):
     mobile = i
     return mobile
    

16. Instead of:

    index = 1
    while True:
     # body
     index += 1
    

    consider using itertools.count:

    for index in itertools.count(1):
     # body
    

17. The functions changeDirections, swap, findLargestMI and printListWithDirections are each called only once, from inside getAllPermutations. This suggests that we don't need to make these into separate functions, we could just inline them at their point of use.

    Inlining like this isn't always a good idea — sometimes having lots of small functions is better because each one can be understood and tested individually. Take a look at the revised code below and see which style you prefer.

2. Revised code

from itertools import count
# Directions in which an element may be moving.
_LEFT = -1
_RIGHT = 1
class PermutationElement:
 "Element of a permutation, with its current direction."
 def __init__(self, element, direction):
 assert direction in (_LEFT, _RIGHT)
 self.element = element
 self.direction = direction
# Mapping from direction to corresponding format string.
_FORMAT = {_LEFT: " <{}", _RIGHT: " {}>"}
def print_permutations(iterable):
 "Print the permutations of an iterable in plain changes order."
 # Build initial state, with all elements moving left.
 permutation = [PermutationElement(element, _LEFT) for element in iterable]
 for n in count(1):
 # Print the permutation.
 print("{}.".format(n), end="")
 for e in permutation:
 print(_FORMAT[e.direction].format(e.element), end="")
 print("")
 # Find the index of the largest mobile element in the permutation.
 mobile = None
 for i, e in enumerate(permutation):
 j = i + e.direction
 if (0 <= j < len(permutation)
 and e.element > permutation[j].element
 and (mobile is None or e.element > mobile_element)):
 mobile = i
 mobile_element = permutation[mobile].element
 if mobile is None:
 print("#####END#####")
 break
 # Reverse direction of elements larger than the mobile element.
 for e in permutation:
 if e.element > mobile_element:
 e.direction *= -1
 # Update permutation by moving the mobile element in its direction.
 i = mobile
 j = i + permutation[i].direction
 assert 0 <= j < len(permutation)
 permutation[i], permutation[j] = permutation[j], permutation[i]
if __name__ == '__main__':
 n = int(input("How many elements? "))
 print_permutations(range(1, n + 1))

• Onur C.Y.: Amazing! Thank you very much for your effort and sorry that i couldn't answer earlier!