permutations

import Data.List as List

makePairs :: [Int] -> [(Int, [Int])]
makePairs [] = []
makePairs l = map (\x -> (x, filter (/= x) l)) l

mapFst :: (a -> b) -> [(a, c)] -> [(b, c)]
mapFst _ [] = []
mapFst f ((x, y): xs) = (f x, y): (mapFst f xs)

mapSnd :: (a -> b) -> [(c, a)] -> [(c, b)]
mapSnd _ [] = []
mapSnd f ((x, y): xs) = (x, f y): (mapSnd f xs)

flatMap :: (a -> b -> b) -> [(a, [b])] -> [b]
flatMap _ [] = []
flatMap f (x: xs) = (map (f $ fst x) (snd x)) ++ flatMap f xs

genPermutationHelper :: [Int] -> [[Int]]
genPermutationHelper [] = [[]]
genPermutationHelper s = applied where
    pairs = makePairs s
    unapplied = mapSnd genPermutationHelper pairs
    applied = flatMap (\x l -> x:l) unapplied

genPermutations :: Int -> [[Int]]
genPermutations n = genPermutationHelper [1..n]


showList' :: (Show a) => [a] -> String
showList' [] = ""
showList' l = concat $ List.intersperse " " (map show l)

main = do
    s <- getLine
    let n = read s :: Int
    let permutations = genPermutations n
    print $ length permutations
    sequence_ $ map (putStrLn . showList') permutations