Cayley距離 (Cayley distance) †一方の順序の任意の要素対を交換する手続きによってもう一方の順序に変換するとき,その最小交換回数. Kendall距離は隣接する対しか交換しないが,Cayleyでは隣接していなくてもよい. Cayley距離は距離の公理をみたすmetric. 完全に一致するとき最小値 0. Kendall距離やFootrule距離との間にDiaconis-Grahamの不等式が成立.
「互いに逆順序のときに最大値をとる」は間違いでは? おそらく、Cayley距離の計算はNP完全では? 教科書 p.25 を読んでみました.端から順に正しいものと入れ替えていけばいいようで,\(O(n)\) で計算できるそうです.また面白いことに,順序のなかで入れ替わりの循環の数を数えて,長さから引くと Cayley距離になるそうです. -- しましま 関連項目 †リンク集 †
関連文献 † |