Steinhaus-Johnson-Trotter Algorithm

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.

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