Haskell: đảo ngược một hoán vị trong thời gian tuyến tính, sử dụng chỉ liệt kê

Question

Tôi muốn xác định một hàm

invert :: [Int] -> [Int] 

rằng giả định rằng đầu vào của nó là một hoán vị của [0..(n-1)], và trả về nghịch đảo của nó. Có thể xác định nó bằng cách sử dụng chỉ danh sách và bộ dữ liệu (không có mảng) để nó chạy trong thời gian tuyến tính?

Điều này chủ yếu là vì lợi ích học tập; trong mã thực, tôi có thể sử dụng Array hoặc STArray hoặc tương tự.

Answer 1

Không chắc chắn về thời gian tuyến tính, chỉ là ghi chú mới bắt đầu.

λ> (\x -> map snd $ sort $ zip x [1..(length x)]) [3,8,5,10,9,4,6,1,7,2] 
[8,10,1,6,3,7,9,2,5,4] 

Answer 2

Dường như với tôi rằng bạn không thể làm điều này trong thời gian tuyến tính. Để thực hiện với độ phức tạp thời gian O (n), bạn sẽ cần phải tạo danh sách kết quả theo thứ tự mà bạn không thể thực hiện trực tiếp với các danh sách khuyết điểm, tôi giả sử.

Answer 3

Vì vậy, điều này không sử dụng "danh sách duy nhất". Nhưng nó có vẻ vừa vặn.

import qualified Data.Vector as V 

invert :: [Int] -> [Int] 
invert list = V.toList $ vec V.// assocs 
    where vec = V.fromList list -- better ideas for initializing vec? 
     assocs = zip (map pred list) [1..] 

Xem the Vector package, mà tuyên bố rằng // là O (n). Vâng, nó nói O (n + m), nhưng trong trường hợp này là n = m.

Tôi tải nó lên thành ghci và nhận được câu trả lời giống như dmitry. :)

Answer 4

Nếu hoán vị được thể hiện dưới dạng danh sách các chu kỳ rời nhau, sau đó

invert :: [[Int]] -> [[Int]] 
invert = map reverse 

chạy trong thời gian tuyến tính. Tôi không chắc chắn nếu có một cách tuyến tính để chuyển đổi qua lại giữa các đại diện khác nhau, mặc dù.

Answer 5

Như có vẻ không phải là một câu trả lời tích cực cho câu hỏi thực tế, tôi sẽ thêm cheat của tôi vào danh sách các phi giải pháp:

invert :: [Int] -> [Int] 
invert lst = take lng $ map (fromIntegral.(`mod`h)) $ iterate (`div`h) 
       $ sum $ zipWith (\k x->k*h^x) [0..] lst 
    where h::Integer 
     h = fromIntegral lng 
     lng = length lst