長さnのリストに作用する置換

Question

数学では、長さnのリストを並べ替えるときは、並べ替えを使ってリストに作用します。例：

(1 2) * (x, y, z) = (y, x, z) 
(1 n 2) * (v[1], v[2], ..., v[n]) = (v[n], v[1], ..., v[2]) 
perm * (v[1], v[2], ..., v[n]) = (v[perm(1)], v[perm(2)], ..., v[perm(n)]) 

ハスケルでこれを行うにはどうすればよいですか？

Answer 1

古いインデックスから新しいインデックスへのマップを作成するために、入力順列を使用します。

import Prelude hiding ((*)) 
import qualified Data.Map as M 

infixr 5 * -- right-associative so we can compose permutations conveniently 

(*) :: [Int] -> [a] -> [a] 
perm * xs = zipWith (\i _ -> xs !! M.findWithDefault i i ixMap) [0..] xs 
    where ixMap = M.fromList (zip perm (drop 1 perm ++ take 1 perm)) 

あなたはGHCiのプロンプトでのアクションでそれを見ることができます（それが使用するプログラミングではいつものようにかかわらず、1ベースのインデックスではなく、0をベース）：

> [0,1] * "xyz" 
"yxz" 
> [0,4,1] * "abcde" 
"eacdb" 

これは（N^2 Oコストlog m）ここで、nはxsの長さであり、mはpermの長さです。 xsへのインデックス付けの場合は、(!!)からM.lookupに切り替えることで、これをO（n log（nm））に減らすことができます。