from typing import List
from typing import Tuple


def generateNeighbourhood(cities):
    """Generates all 2-opt permutations of `cities` with respect to TabuSearch.

    This function doesn't touch the first and the last city to preserve
    the natural TSP cycle.
    """
    forbidden_swaps: List[Tuple] = []
    neighbourhood: List[List[int]] = []
    for i in range(1, len(cities) - 1):
        for j in range(i, len(cities) - 1):
            neighbour = list(cities)
            if (neighbour[i], neighbour[j]) in forbidden_swaps:
                continue
            forbidden_swaps.append((neighbour[i], neighbour[j]))
            # swap two cities
            neighbour[i], neighbour[j] = neighbour[j], neighbour[i]
            neighbourhood.append(neighbour)
    return neighbourhood