Given 2 lists of unique, orderable, non-contiguous elements, say:
['d', 'a', 'z', 'b']
I want to find their index in another list, say:
['a', 'b', 'z', 'd']
The result would be a list with their positions:
[3, 0, 2, 1] -- element at 0 is at 3,
-- element at 1 is at 0, etc.
This can be also done in O(n log n) time with a couple of sorts. I assume that the second list is a permutation of the first one.
import Data.List
import Data.Ord
import Data.Function
correspIx :: Ord a => [a] -> [a] -> [(Int, Int)]
correspIx = zip `on` map fst . sortBy (comparing snd) . zip [0..]
correspIx returns a list of pairs with the indices corresponding to each other:
correspIx "dazb" "abzd" == [(1,0),(3,1),(0,3),(2,2)]
We need another sort to get the result indicated in the question:
correspIx' :: Ord a => [a] -> [a] -> [Int]
correspIx' xs ys = map snd $ sortBy (comparing fst) $ correspIx xs ys
Now correspIx' "dazb" "abzd" == [3,0,2,1].
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments