nickrolfe · July 3, 2010 14:27
diff --git a/gistfile1.hsc b/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)
	-- 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)