CODEWITHSUNDEEP
algorithmhaskell
Polymer
Polymer

Reputation: 1063

permutations acting on lists of length n

In math, when I want to rearrange a list of length n, I'll act on the list with a permutation. For example:

(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)] )

How would I do this in Haskell?

Upvotes: 0

Views: 79

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 152707

I would use the input permutation to build a map from old indices to new indices.

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))

You can see it in action in the ghci prompt (though as usual in programming it uses 0-based rather than 1-based indexing):

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

This costs O(n^2 log m) where n is the length of xs and m is the length of perm. You can reduce this to O(n log(nm)) by switching from (!!) to M.lookup for the indexing into xs, too.

Upvotes: 2

Related Questions