हास्केल: रैखिक समय में एक क्रमपरिवर्तन को उलटने के लिए, केवल सूचीबद्ध करता

Question

मैं एक समारोह

invert :: [Int] -> [Int] 

कि मानता है कि अपने इनपुट [0..(n-1)] का क्रमपरिवर्तन है, और उसके प्रतिलोम देता है परिभाषित करना चाहते हैं का उपयोग कर। क्या कोई इसे केवल सूचियों और tuples (बिना सरणी के) का उपयोग कर परिभाषित कर सकता है ताकि यह रैखिक समय में चलता है?

यह मुख्य रूप से अकादमिक हित से बाहर है; वास्तविक कोड में मैं Array या STArray या इसी तरह का उपयोग कर सकता हूं।

Answer 1

रैखिक समय, बस एक शुरुआती नोट के बारे में निश्चित नहीं है।

λ> (\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

ऐसा लगता है कि आप इसे रैखिक समय में नहीं कर सकते हैं। ओ (एन) समय जटिलता के साथ कार्यान्वयन के लिए आपको परिणाम सूची से परिणाम सूची बनाना होगा, जिसे आप सीधे विपक्ष सूची के साथ नहीं कर सकते हैं, मुझे लगता है।

Answer 3

तो, यह "केवल सूचियों" का उपयोग नहीं करता है। लेकिन यह बहुत अच्छा लग रहा था।

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

जो दावा है कि //हे (एन) है the Vector package देखें। खैर, यह ओ (एन + एम) कहता है, लेकिन इस मामले में, n = m।

मैंने इसे ghci में लोड किया और उसी जवाब को डिमिट्री के रूप में मिला। :)

Answer 4

क्रमपरिवर्तन, तो शिथिल चक्रों की सूची के रूप में प्रतिनिधित्व कर रहे हैं

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

रैखिक समय में चलाता है। मुझे यकीन नहीं है कि अलग-अलग प्रतिनिधित्वों के बीच आगे और आगे परिवर्तित करने के लिए एक रैखिक तरीका है या नहीं।

Answer 5

वहाँ वास्तविक प्रश्न के लिए एक सकारात्मक जवाब नहीं लगता है के रूप में, मैं गैर समाधान की सूची में मेरा धोखा जोड़ देंगे:

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