transpositions

def compute_transpositions(start: list, end: list):
    transpositions = []
    size, start = len(start), start[:]
    for pivot in range(size-1): # when list has only one item left, then it's already over
        index = start.index(end[pivot])
        if pivot != index:
            transpositions.append((pivot, index))
            temp = start[pivot]
            start[pivot] = start[index]
            start[index] = temp

    return transpositions

def apply_transpositions(start: list, transpositions: typing.List[typing.Tuple[int, int]]):
    for tp in transpositions:
        temp = start[tp[0]]
        start[tp[0]] = start[tp[1]]
        start[tp[1]] = temp

    return start