[Haskell-cafe] Construct all possible trees
andrewcoppin at btinternet.com
Wed Jun 13 16:17:20 EDT 2007
Colin DeVilbiss wrote:
> On 6/12/07, Andrew Coppin <andrewcoppin at btinternet.com> 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?
> 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
More information about the Haskell-Cafe