Menu
I want to define a function
invert :: [Int] -> [Int]
that assumes that its input is a permutation of [0..(n-1)], and returns its inverse. Can one define it using only lists and tuples (without arrays) so that it runs in linear time?
This is primarily out of academic interest; in real code I might use Array or STArray or similar.
593
To find the inverse of a permutation just write it backwards. If τ=(1243)(67) then τ−1=(76)(3421) which can then be rewritten as τ−1=(1342)(67).
An inverse permutation is a permutation obtained by inserting the position of all elements at the position equal to the respective values of the element in the array. Explanation: The inverse permutation of the given array is {1, 4, 3, 2} which is same as the given array.
An ambiguous permutation is a permutation which cannot be distinguished from its inverse permutation. The permutation 1, 4, 3, 2 for example is ambiguous, because its inverse permutation is the same.
Not sure about linear time, just a beginner note.
λ> (\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]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
