Are there standard or known weights/metrics on cyclic orders?
Cyclic orderings are different ways of listing elements from a finite set, where you call two lists the same if they differ only by a rotation. For example, the ways that 4 people can sit at a circular table, where you ignore rotation of the table.
So the following 4 rankings of a 4-item set should be considered the same:
[2,1,4,3] [1,4,3,2] [4,3,2,1] [3,2,1,4]
You can think of this as arranging the 4 items on a circular list, with no particular top, but a definite direction.
I would like to compare different cyclic orderings in a meaningful way. I have learned that there are many well-known ways of assigning distance or weight to non-cyclic orderings (a.k.a. permutations!). For example:
- Kendall $\tau$
- Transposition distance (Cayley)
- Ulam metric
- Hamming weight
- $\ell_1$ norm
But these give different weights to permutations which correspond to the same cyclic ordering.
A first simple idea is the following: given a permutation $a$, count the number of $i$ such that $a(i+1) \neq a(i) +1$, where $0 \leq i \leq n$ and index addition is performed modulo $n$.
A natural variation on this idea would sum $|a(i+1) - (a(i)+1)|$.
I haven't thought about either of these too carefully yet. Do they appear in the literature somewhere? Some nontrivial internet searching hasn't turned anything up.