from typing import Sequence, Literal, Set, Tuple from copy import deepcopy def isNearlySorted(L: Sequence[float]) -> Literal[False] | Sequence[float]: """Returns a tuple of indices that need to be swapped to sort the list, or False if it cannot be sorted with a single swap.""" if not len(L): return False sortPath: Set[Tuple[int, int]] = set() sortedList = list(deepcopy(L)) for i in range(len(L) - 1): for j in range(len(L) - 1, i, -1): a = sortedList[i] b = sortedList[j] if a > b: sortedList[i], sortedList[j] = b, a sortPath.add((i, j)) if len(sortPath) > 1: return False if len(sortPath) == 1: return list(sortPath.pop()) return False print("Testing isNearlySorted()...", end="") assert isNearlySorted([2, 7, 5, 4]) == [1, 3] assert isNearlySorted([2, 3, 1]) == False assert isNearlySorted([1, 2, 3]) == False assert isNearlySorted([-1, 1, 0, 5]) == [1, 2] assert isNearlySorted([5, 6, 9, 8, 8]) == [2, 4] assert isNearlySorted([2, 1]) == [0, 1] assert isNearlySorted([3, 3]) == False assert isNearlySorted([2]) == False assert isNearlySorted([]) == False # Verify that the function is non-mutating L = [2, 7, 5, 4] isNearlySorted(L) assert L == [2, 7, 5, 4] print("Passed!")