gistfile1.hsc

-- Compute all n! permutations of a list of n objects
-- 
-- The algorithm is Method 1 from Knuth's The Art of Computer Programming
-- Volume 1, Chapter 1, Section 1.2.5 Permutations and Factorials.

-- Given an object x and a list of objects ys of length n, insert will return a
-- list of n+1 lists by inserting x in all posssible places in ys.
-- e.g. insert 1 [2,3,4] returns the following:
-- [[1,2,3,4], [2,1,3,4], [2,3,1,4], [2,3,4,1]]

insert :: a -> [a] -> [[a]]
insert x []        = [[x]]
insert x zs@(y:ys) = (x:zs) : map (y :) (insert x ys)

-- The base case is trivial.
-- The inductive case inserts the head of the list in every position (by
-- calling insert x) of all permutations of the tail.

perms :: [a] -> [[a]]
perms []     = [[]]
perms (x:xs) = concatMap (insert x) (perms xs)