Cayley距離

Cayley距離 (Cayley distance) †

一方の順序の任意の要素対を交換する手続きによってもう一方の順序に変換するとき，その最小交換回数． 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距離になるそうです． -- しましま

関連項目 †

• Cayley distance
   
• 距離
• 順序の距離
• Spearman距離
• Footrule距離
• Kendall距離
• Ulam距離
• Diaconis-Grahamの不等式
   
• 検索:Cayley距離

リンク集 †

• Cayley distance @ KARDI TEKNOMO

関連文献 †

• Book/Analyzing and Modeling Rank Data 2.5.1節