I need to call this perms
function in this nested way:
e = [1,3,7,10, 25,50]
f = perms (perms (perms (perms (perms (perms [[]] e) e) e) e) e) e
g = [[]] ++ f -- final set of permutations
perms :: (Eq a, Ord a) => [[a]] -> [a] -> [[a]]
-- set [a] is a set of existing permutations and set [b] are the elements to add to [a] in all possible permutations
perms xss [] = xss -- no unique elements to create new permutations from
perms [xs] ys = [xs ++ [y] | y <- ys \\ xs ] -- last list of xs in list xss
perms (xs:xss) ys = [xs] ++ [ xs ++ [y] | y <- ys\\xs ] ++ perms xss ys
In short I'm wondering if there is a function like a fancy use of map with
(.)
or something
which can do six of these nested calls for me in a cleaner syntax than:
f = perms (perms (perms (perms (perms (perms [[]] e) e) e) e) e) e
I'm confident I could add another Int
argument to the perms
function for counting through the P(n, r) for r <- [1..6] but that's not of interest to me here. I'm wondering how I can do 6 nests of the same function calling itself recursively without the literal nesting?
But maybe it comes down to a bad choice of recursion design in my function and whole approach needs to be scrapped for something better?
Background:
This is me trying to work out a part of the Countdown game solution finder posited in this Graham Hutton Introduction to Haskell lecture. (His solution here which is more elegant I'm sure)
Using the Data.List library permutations
function doesn't work, because in addition to the (n=720) 6-element permutations, I need the (720) 5-element permutations, the (360) 4-element permutations, the (120) 3-element permutations …, the (6) 1 element permutations and a null set solution. Because in this game you can use as many or few of the 6 numbers randomly selected as you wish.
I looked at the source code for permutations
on hackage.org and it's a bit beyond my comprehension. So I thought I'd better try rolling this one for myself.
This is Hutton's solution for finding the choices of number permutations which I've only just chosen to look at.
-- Combinatorial functions
subs :: [a] -> [[a]]
subs [] = [[]]
subs (x:xs) = yss ++ map (x:) yss
where yss = subs xs
interleave :: a -> [a] -> [[a]]
interleave x [] = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = concat (map (interleave x) (perms xs))
choices :: [a] -> [[a]]
choices = concat . map perms . subs
I would use
iterate
, as in