without :: Eq a => [a] -> [a] -> [a]
without a [] = a
without a (x:xs) = filter (/=x) a `without` xs

dis :: [Int] -> [[Int]]
dis = dis' [[]] 1
    where
        dis' s k p = if k == -1
                         then init s
                         else dis' s' k' p
            where
                s' = if k'' `elem` visited
                         then s ++ [[k']]
                         else (init s) ++ [(last s ++ [k'])]

                k' = if k'' `elem` visited
                         then next s k
                         else get p k

                k'' = get p k
                next s k = head $ ([1..length p] `without` (visited)) ++ [-1]
                visited = concat s
                get p k = p !! (k-1)

main = do
    let perm1 = [3, 2, 4, 1, 5]
    let perm2 = [1, 2, 3, 4, 5]
    let perm3 = [2, 3, 4, 5, 1]
    print $ dis perm1
    print $ dis perm2
    print $ dis perm3