The Burrows-Wheeler transform¹ (BWT) is a reversible permutation of the characters of a string. It was originally invented for use in compression. The BWT of a string is obtained by first taking all rotations of the string. For example, all rotations of the string abab$ are

abab$, bab$a, ab$ab, b$aba, $abab

These rotations are then sorted lexicographically

$abab, ab$ab, abab$, b$aba, bab$a

The BWT of the string is defined as the string resulting from concatenating the last characters of each rotated string in this lexicographical order. So BWT(abab$) = bb$aa for the example string.

Assignment

• Write a function rotate that takes a string $$s$$. The function also has an optional Boolean parameter left (default value: True). The function must return the left rotation of $$s$$ if left is True and the right rotation if left is False. The left rotation of $$s$$ is obtained by moving the first character of $$s$$ to the end. The right rotation of $$s$$ is obtained by moving the last character of $$s$$ to the front.

• Write a function rotations that takes a string $$s$$. The function also has an optional Boolean parameter left (default value: True). The function must returns a list containing all rotations of $$s$$. The list should start with $$s$$ and each other element of the list should be the left of right rotation of its predecessor, depending left being True or False.

• Write a function bwm that takes a string $$s$$ and returns a list containing all rotations of $$s$$ in lexicographical order.

• Write a function bwt that takes a string $$s$$ and returns $$\text{BWT}(s)$$.

Example

>>> rotate('abab$')
'bab$a'
>>> rotate('abab$', left=False)
'$abab'

>>> rotations('abab$')
['abab$', 'bab$a', 'ab$ab', 'b$aba', '$abab']
>>> rotations('abab$', left=False)
['abab$', '$abab', 'b$aba', 'ab$ab', 'bab$a']

>>> bwm('abab$')
['$abab', 'ab$ab', 'abab$', 'b$aba', 'bab$a']

>>> bwt('abab$')
'bb$aa'