I knew there was a tighter way to write the derangement code for my assignment, but my Haskell was really rusty and what I had was fast, so I gave up. This morning it came to me – now I have 5 lines instead of 8. I do not have any idea how one would express this in pseudo code, though and it’s probably really quite difficult to read if you’re not familiar with Haskell.
derange1 :: Int -> [[Int]]
derange1 x = perm 0 (makeList x)
makeList :: Int -> [Int]
makeList 0 = []
makeList n = makeList (n-1) ++ [n]
perm :: Int -> [Int] -> [[Int]]
perm _ [] = [[]]
perm x list = concat [map (e:) (perm (x+1) (delete e list)) |
e <- list, e /= (x+1)]
It’s sometimes surprising how having less can 1) be more work and 2) feel like such an achievement.