Re: [Haskell-cafe] Construct all possible trees

Colin DeVilbiss wrote:

On 6/12/07, Andrew Coppin wrote:

Based on the sample output, I'm guessing that the desired output is "every tree which, when flattened, gives a permutation of a non-empty subset of the supplied list". This limits the output to trees with up to "n" leaves.

Every possible tree, using the supplied elements as leaf elements, without ever duplicating them. (Note, however, that the initial list may contain duplicates in the first place, so you can't just test for and remove duplicates in the produced lists; you must avoid repeating elements by construction.)

...

Branch (Branch (Leaf 1) (Leaf 3)) (Leaf 1),

If I'm guessing the desired output correctly, this must be a typo?

Erm... yes.

I'd be tempted to solve the "list-only" problem first (generate all "sub-permutations" of a list), then solve the tree problem (generate all "un-flattenings" of a list).

I can already create all possible 2-element trees. It seems like there should be a way to recurse that... but without duplicating elements. Hmm, I don't know - there's probably several correct solutions to this problem. ;-)