valid_perms :: num -> [[num]]
|| solves Amro Al-Deeb's puzzle!
|| You give it the number it goes up to, e.g. 3 means find the permutations of
|| [1,1,2,2,3,3] with the 1's separated by 1, the 2's by 2, and the 3's by 3.

	valid_perms n = filter is_valid (perms ([1..n]++[1..n]))
			where
			is_valid perm = map (separation perm) [1..n] = [1..n]



perms :: [*] -> [[*]]
|| finds all permutations of a list

	perms [] = [[]]
	perms (h:t) = mkset (sort (concat (map (all_insertions h) (perms t))))



all_insertions :: * -> [*] -> [[*]]
|| auxiliary function for use by perms
|| finds all insertions of one new element into a list

	all_insertions x [] = [[x]]
	all_insertions x (h:t) = (x:h:t) : map (h:) (all_insertions x t)



positions :: * -> [*] -> [num]
|| finds all positions (numbered from zero) of an element in a list
|| e.g. positions 'c' "catacombs" = [0,4]

	positions x [] = []
	positions x (h:t) = 0 : map (1+) (positions x t), if x=h
			  =     map (1+) (positions x t), if x~=h



separation :: [*] -> * -> num
|| finds the separation (for purposes of Amro Al-Deeb's puzzle) of the two
|| occurrences of an element in a list. There had better be exactly two!

	separation list x = abs(hd p - hd(tl p)) - 1, if #p = 2
			  = error "not two copies of element!", if #p ~= 2
			    where
			    p = positions x list
