# Distances on generalizations of the symmetric group

I'm a computer vision student, and I'm looking for some symmetric group literature guidance. I'm going to provide some context, and finally ask two questions.

The Cayley distance and other distances on permutations ($S_n$) are quite useful in applied machine learning; see the beginning of this paper for some examples of distances on $S_n$. Typically, such distances are used when the absolute intensities of measurements are meaningless, but the relative intensities are meaningful. For example, if I wanted to compare the colors of pixels in a natural scene from an RGB image, I would not directly consider the absolute values of the R, G, and B components, as such values are sensitive to lighting. Instead, I would consider the differences in the ratios of R to G, R to B, etc. In the extreme case, I might only care about the ranking of the intensities of the color channels. The ranking is a permutation, so I could compare colors using a permutation distance.

This approach falls down when there is ambiguity in the ranking, as the ambiguity is a source of noise. For example, for a purely green pixel (R = 0, G = 255, B = 0), the rankings R <= B <= G and B <= R <= G are equally valid. So if I don't choose the rankings consistently, identical pixels may have nonzero distance (breaking a metric axiom).

Even if I choose rankings consistently (say I choose the unique stable sort), weird behavior can arise; consider the pixels {0, 0, 255} and {255, 0, 0}. In the "spirit" of the Cayley distance, these pixels should have a distance of one: swap the R and B channels. This corresponds to the sorts G <= R <= B and G <= B <= R, which differ by one swap. However, the stable sorts are R <= G <= B and G <= B <= R, which has a Cayley distance of two.

Finally, my questions: 1) What generalization of $S_n$ are there that explicitly account for repeated elements? To give a flavor of what I'm asking for, one possible generalization could replace the single-row representation of a permutation, e.g. [1, 3, 4, 2], with a single row of rows representation, e.g. [, [3, 4], ]. This latter representation would represent the sorts for [100, 255, 127, 127]. Of course, people smarter than myself will have thought about this and come up with a better solution. 2) For a given generalization, what are some common distances on it?

• The things you're discussing aren't groups. – Sue Sep 10 '12 at 17:58
• Sue, I think you're right that I'm not talking about a group. Instead, I think it's a monoid, with e.g. [, , ] the identity element for sorts of 3 elements. Since it doesn't have inverses, the standard recipe for computing the Cayley distance breaks down: for permutations $a$ and $b$, the Cayley distances is $n - C(a \cdot b^{-1})$, where $C(x)$ is the number of cycles in $x$. Is this a fatal flaw? – emchristiansen Sep 10 '12 at 20:20
• Douglas, I don't understand your comment. The underlying measurements are probably from a nice set like the integers, not something on which only a strict weak ordering exists. Perhaps you meant a strict weak ordering could be defined for the generalized permutations? But an ordering isn't what I'm after. – emchristiansen Sep 10 '12 at 20:23
• The "set" for the strict weak order in your example is $\lbrace R,G,B \rbrace.$ The possible values assigned to each element of the set are totally ordered. – Douglas Zare Sep 10 '12 at 20:35

I think the generalization you want is a total preorder, or equivalently a strict weak ordering. On finite sets, these correspond to the orderings of values of a function from the set to $\mathbb{R}$. In a total preorder, if $f(x) = f(y)$ then you say $x \le y$ and $y \le x$. In a strict weak order, if $f(x) = f(y)$ then you say neither $x \lt y$ nor $y \lt x$.
Strict weak orders are in bijection with the faces of a permutohedron whose $1$-skeleton is identified with the Cayley graph of adjacent transpositions (by inverting the permutations). The dimension of a face is the number of equalities. The distance you want might be the distance in a graph $G$ whose vertices are the faces of the permutohedron where each face is adjacent to the faces of one lower dimension it contains and the faces of one higher dimension which contain it.
This distance on $G$, restricted to the $0$-dimensional faces, is at most twice the Cayley distance, since you can achieve a transposition in two steps, moving from $a \lt b \lt c$ to $a \lt b = c$ to $a \lt c \lt b$. However, the macroscopic properties of this distance are quite different from those of the Cayley graph because you can take big shortcuts through high dimensional faces. To reverse $a \lt b \lt c$ takes $3$ transpositions but only $4$ steps in $G$: $a \lt b \lt c$, $a \lt b = c$, $a=b=c$, $b=c\lt a$, $c \lt b \lt a$. Every face is of distance at most $2(n-1)$ from every other face since every face is of distance at most $n-1$ from the $n-1$-dimensional face in which all coordinates are equal.
So, another possible distance on $G$ is to declare that the length of an edge is the number of pairwise inequalities added or subtracted. Adjacent faces are related by merging two equivalence classes or dividing one into two. If an edge merges two equivalence classes of sizes $m_1$ and $m_2$, then let the length of that edge be $m_1\times m_2$. So, the distance between $a\lt b=c$ and $a=b=c$ is $2$, and the path of $4$ edges from $a\lt b\lt c$ to $c \lt b \lt a$ has length $6$. If you restrict this distance to the vertices of the permutohedron, you get twice the Cayley distance.