順列の最小完全ハッシュ関数 - Qiitaこの記事は文字列アルゴリズム Advent Calendar 2017 24日目の記事です. 今日 12/24 が何の日か，みなさんもちろん知っていますよね？そう，アッカーマン関数で有名な Wilhelm Friedrich Ackermann1の没日です．計算理論に多大な貢献をしたアッカーマンに縁のある日に記事を書くということで，身が引き締まる思いです． さて，この記事では同じ文字が二度現れない文字列とみなすこともできる順列に関して，その最小完全ハッシュ関数のお話をします. TL;DR 順列の辞書順最小完全ハッシュ関数・逆関数の計算は $O(N \log N)$ でできる．(計算モデルを仮定すると高速化可能) 辞書順を諦めると，順列の最小完全ハッシュ関数・逆関数の計算は $O(N)$ でできる． 定義 順列 (Permutation) 順列，あるいは置換 (Permutation) とは
