* Cayley距離 (Cayley distance) [#ae17d197]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

一方の順序の任意の要素対を交換する手続きによってもう一方の順序に変換するとき,その最小交換回数.
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)\)~
(こびとさん)

[[教科書>Book/Analyzing and Modeling Rank Data]] p.25 を読んでみました.端から順に正しいものと入れ替えていけばいいようで,\(O(n)\) で計算できるそうです.また面白いことに,順序のなかで入れ替わりの循環の数を数えて,長さから引くと Cayley距離になるそうです. -- しましま

**関連項目 [#l7434761]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[Cayley distance]]
#br
-[[距離]]
-[[順序の距離]]
-[[Spearman距離]]
-[[Footrule距離]]
-[[Kendall距離]]
-[[Ulam距離]]
-[[Diaconis-Grahamの不等式]]
#br
-[[検索:Cayley距離]]

**リンク集 [#j3b4b987]

//関連するWWW資源があればリンクしてください.
-[[Cayley distance>http://people.revoledu.com/kardi/tutorial/Similarity/CayleyDistance.html]] @ KARDI TEKNOMO

**関連文献 [#h616a79e]

//この%項目%に関連する書籍や論文を紹介してください.

-[[Book/Analyzing and Modeling Rank Data]] 2.5.1節

トップ   編集 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS