Andrew Coppin
Jon Fairbairn wrote:
I'm trying to construct a function
all_trees :: [Int] -> [Tree]
such that all_trees [1,2,3] will yield
[ Leaf 1, Leaf 2, Leaf 3, Branch (Leaf 1) (Leaf 2), Branch (Leaf 1) (Leaf 3), Branch (Leaf 2) (Leaf 1), Branch (Leaf 2) (Leaf 3), Branch (Leaf 3) (Leaf 1), Branch (Leaf 3) (Leaf 2), Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3), Branch (Branch (Leaf 1) (Leaf 3)) (Leaf 1), Branch (Branch (Leaf 2) (Leaf 1)) (Leaf 3), Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 1), Branch (Branch (Leaf 3) (Leaf 1)) (Leaf 2), Branch (Branch (Leaf 3) (Leaf 2)) (Leaf 1), Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)), Branch (Leaf 1) (Branch (Leaf 3) (Leaf 2)), Branch (Leaf 2) (Branch (Leaf 1) (Leaf 3)), Branch (Leaf 2) (Branch (Leaf 3) (Leaf 2)), Branch (Leaf 3) (Branch (Leaf 1) (Leaf 2)), Branch (Leaf 3) (Branch (Leaf 2) (Leaf 1)) ]
Why does it stop there? That's not all the trees, surely?
Really? OK, what other trees do *you* think you can construct from the numbers 1, 2 and 3?
Oh, you mean "with each member of the list appearing at most once"? Why didn't you /say/ so? :-P Trees with all the elements of a list in that order:
the_trees:: [Integer] -> [Tree] the_trees [x] = [Leaf x] the_trees l = zipWith Branch (concat (map the_trees (tail $ inits l))) (concat (map the_trees (tail $ tails l)))
combinations [] = [] combinations (h:t) = [h]:combinations t ++ (concat $ map insertions $ combinations t) where insertions l = zipWith (\a b -> a ++ h: b) (inits l) (tails l)
Trees with all the members of a list appearing at most once (in any order)
combination_trees l = concat $ map the_trees $ combinations l
* * * It looks like Lennart was writing something very similar at the same time as me. That obviously means that this is the /right/ approach :-). As with his version, the order isn't exactly as you listed them, but it's not far off ... -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk