In this chapter we will represent a chromosome as a signed permutation: a collection of integers with unique absolute values. Each integer represents a synteny block, with the positive/negative sign of the integer indicating the block's direction. The number of integers of a signed permutation is called its length.

Assignment

In this assignment you need to implement the greedy heuristic for sorting by reversals on signed permutations. To do so, you define a class SignedPermutation that represents signed permutations. The objects of this class are immutable and the initialisation method takes one or more integers with a unique absolute value. The class SignedPermutation should support at least the following methods:

• A method reversal that takes two integers $$s$$ and $$e$$. The method should return a new signed permutation (an object of the class SignedPermutation) that results from a reversal of the elements in the slice $$[s:e]$$.

• A method greedy_sort that takes no arguments. The method must return an iterator that yields tuples $$(s, e)$$ that correspond to the reversals that the greedy algorithm makes to sort the signed permutation by reversals.

Make sure the built-in functions repr and str return string representations of objects of the class SignedPermutation that are formatted according to the example given below. In particular, the string representation returned by the repr function should not display the plus signs of the integers, whereas the string representation returned by the str function should explicitly display the plus signs.

Example

>>> permutation = SignedPermutation(-3, +4, +1, +5, -2)
>>> permutation
SignedPermutation(-3, 4, 1, 5, -2)
>>> print(permutation)
(-3 +4 +1 +5 -2)
>>> print(permutation.reversal(0, 3))
(-1 -4 +3 +5 -2)
>>> print(permutation.reversal(2, 4))
(-3 +4 -5 -1 -2)
>>> tuple(permutation.greedy_sort())
((0, 3), (0, 1), (1, 5), (2, 4), (3, 5), (3, 4), (4, 5))

The reversals that the greedy algorithm makes to sort the signed permutation by reversals, results in the following succession of signed permutations (using the string representations as returned by the built-in function str). The reversals themselves have been marked in red.

(-3 +4 +1 +5 -2)
(-1 -4 +3 +5 -2)
(+1 -4 +3 +5 -2)
(+1 +2 -5 -3 +4)
(+1 +2 +3 +5 +4)
(+1 +2 +3 -4 -5)
(+1 +2 +3 +4 -5)
(+1 +2 +3 +4 +5)