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中的列表排列

回答

相關問題