# Steinhaus-Johnson-Trotter Algorithm

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 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()

• What would help understand it faster is a description of what the algorithm is supposed to achieve. Jan 7, 2018 at 21:22
• Yes, of course. The algorithm is supposed to give all possible permutations of n elements. Jan 7, 2018 at 22:08

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 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".

### 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


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))

• Amazing! Thank you very much for your effort and sorry that i couldn't answer earlier! Jan 9, 2018 at 21:02