![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
一方の順序の任意の要素対を交換する手続きによってもう一方の順序に変換するとき，その最小交換回数． Kendall距離は隣接する対しか交換しないが，Cayleyでは隣接していなくてもよい．
Cayley距離は距離の公理をみたすmetric． 完全に一致するとき最小値 0． Kendall距離やFootrule距離との間にDiaconis-Grahamの不等式が成立．
-- しましま
「互いに逆順序のときに最大値をとる」は間違いでは？
長さ3で考えると(1,2,3)と(3,2,1)は逆順ですが、1番と3番を入れ替えればよいのでCayley距離は1です。
一方、(3,1,2)と(1,2,3)を考えると、3個の要素とも順位が異なるので、1回の操作で両者を一致させることはできません。
この例は互いに逆順のときよりもCayley距離が大きくなる場合があることを示しています。
(こびとさん)
おそらく、Cayley距離の計算はNP完全では？
Kendall距離の計算は\(O(n^2)\)
(こびとさん)
教科書 p.25 を読んでみました．端から順に正しいものと入れ替えていけばいいようで，\(O(n)\) で計算できるそうです．また面白いことに，順序のなかで入れ替わりの循環の数を数えて，長さから引くと Cayley距離になるそうです． -- しましま
