Perdistance

Perdistance, short for permutation distance, is a distance measure between two vectors that accounts for all possible re-orderings of coordinates and takes the smallest distance achieved under any permutation. It is used in contexts where the arrangement of features is not fixed or where only the multiset of feature values matters.

Formal definition: Let x and y be vectors in R^n. For each permutation π of {1,...,n}, let P_π be the corresponding permutation matrix. The perdistance between x and y is defined as the minimum over all permutations of the Euclidean distance after permuting one vector: perdistance(x,y) = min_{π} || x - P_π y ||_2. Equivalently, it minimizes sum_i (x_i - y_{π(i)})^2 over all π. Variants can use L1 distance or other norms.

Properties: Perdistance is non-negative and symmetric. If y is a permutation of x, the distance is zero. If the underlying base distance is a metric and the permutation action is isometric, perdistance satisfies the triangle inequality and is a metric. However, the value can depend on the dimensionality and the feasibility of rearrangements, which influences interpretability in some applications.

Computation: A naive implementation that checks all permutations is factorial in time. In practice, the problem is formulated as a linear assignment problem with a cost matrix C where C_{i,j} = (x_i - y_j)^2, and the minimum-cost permutation solves the perdistance. The Hungarian algorithm computes the optimum in O(n^3) time. For large n or special structures, approximate or restricted-permutation methods may be used.

Variants and applications: Variants may restrict permutations to blocks, use partial permutations, or blend permutation distance with other metrics. Applications include pattern recognition with unordered features, matching sensor arrays with permuted channels, and comparing histograms or multisets where feature order is not meaningful.