haskell中的列表排列

我们给出了两个列表xs :: [a]和ys :: [Int]。例如：haskell中的列表排列

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

我们不得不产生一个新的列表zs :: [a]，这样zs是使用ys产生的xs置换。对于上面的例子：

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

说明：“随机”在xs第二位置时，“文本”发生在第三位置和“一些”发生在第一位置。

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

来源

2014-09-28 ignite

'Array'有什么问题？ – 2014-09-28 21:14:18

你可以压缩和排序，或者构建一个'Map Int a'，但是任何一种方式都会产生额外的* log（n）*因子。 – 2014-09-28 21:20:20

假设n很大，比如10^6。我正在寻找一种尽量减少额外内存的解决方案，但仍然保持O（n）的复杂性。 – ignite 2014-09-28 21:28:27

简单分拣两次，来回做这项工作：

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

这样

前奏Data.Ord Data.List模块> F [ “一些”， “随机”，“文本 “] [2，3，1]
[” 随机”， “文本”， “一些”]

（使用想法从this answer）。

由于我们在排序指标Int了两次，你可以使用一些整数排序一样基数排序，对于O（n）的解决方案。

来源

2014-09-28 23:19:33

haskell中的列表排列

回答

相关问题