algorithm - haskell中列表的排列

Question

我们有两个列表 xs::[a] 和 ys::[Int]。例如:

xs = ["some", "random", "text"]
ys = [2, 3, 1]

我们必须生成一个新列表 zs::[a]，这样 zs 是使用 生成的 xs 的排列>是。对于上面的例子:

zs = ["random", "text", "some"]

解释:“random”出现在xs中的第2个位置，“text”出现在第3个位置，“some”出现在第1个位置。

到目前为止，我已经找到了这个解决方案:

f :: [a] -> [Int] -> [a]
f xs ys = getList (listArray (1, n) xs) ys where
  n = length xs
  getList :: Array Int a -> [Int] -> [a]
  getList a ys = [ a ! x | x <- ys]

f 是否有更好的定义来避免使用数组？我正在寻找内存高效的解决方案。如果 xs 是一个大字符串列表，数组是一个糟糕的选择。 f 的时间复杂度可以放宽到 O(n log n)。

Answer 1

只需来回排序两次即可:

import Data.Ord
import Data.List

f :: [a] -> [Int] -> [a]
f xs = map fst . sortBy (comparing snd) . zip xs . 
       map fst . sortBy (comparing snd) . zip ([1..] :: [Int]) 

这样

Prelude Data.Ord Data.List> f ["some", "random", "text"] [2, 3, 1]
["random","text","some"]

(使用来自 this answer 的想法)。

由于我们两次都对 Int 索引进行排序，对于 O(n) 解决方案，您可以使用一些整数排序，如基数排序。