Compute Cayley distance between two rankings

cayley_distance.py

# for two permutations of [0,1,...,n], compute how many swaps (not necessarily adjacent)
# are needed to transform one into the other
# code uses: distance of a permutation from the identity permutation
# equals n - #cycles in the cycle notation of the permutation

def cayley_distance(x,y):
    A = range(len(x))
    inv_y = tuple(y.index(a) for a in A)
    comp = tuple(x[inv_y[a]] for a in A)
    cycles = 0
    rem = set(A)
    while rem:
        a = rem.pop()
        cycles += 1
        while comp[a] in rem:
            a = comp[a]
            rem.remove(a)
    return len(A) - cycles
  
assert cayley_distance([0,1,2,3],[1,0,2,3]) == 1
assert cayley_distance([0,1,2,3],[1,0,3,2]) == 2
assert cayley_distance([2,1,3,0],[0,3,1,2]) == 2