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. [[1]
, [3, 4], [2]]. 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?