# algorithm to extract "possibilities" from a tree

From a given tree, subsequent trees have to be generated. Nodes can be marked as "variant" in the given tree (the example uses an asterisk to mark the node). All possible combinations between the variants form the resulting trees.

From the following tree:

``````- Product
- Packaging *
- Small box
- Heavy box *
- Eco
- Non-eco
- Delivery *
- Standard
- Express
``````

The following 6 trees should be generated:

``````- Product
- Packaging
- Small box
- Delivery
- Standard

- Product
- Packaging
- Small box
- Delivery
- Express

- Product
- Packaging
- Heavy box
- Eco
- Delivery
- Standard

- Product
- Packaging
- Heavy box
- Eco
- Delivery
- Express

- Product
- Packaging
- Heavy box
- Non-eco
- Delivery
- Standard

- Product
- Packaging
- Heavy box
- Non-eco
- Delivery
- Express
``````

Is there an elegant algorithm for this (recursive solution)?

• So is the idea that you are selecting only one child node if the children are leaves of the tree? If there was a 4th layer to the tree, would it be treated like the second level or the third level? Commented Dec 24, 2012 at 20:06
• they would be treated as the third level I guess, so if "heavy box" would have childs "small" and "large", there would be 6 new trees in total to be generated... that's the difficult part, that's why I am stuck :) Commented Dec 24, 2012 at 20:23
• Could you use a look ahead and if you've reached the leaf nodes then you are merely selecting each possible value while at any higher level you are taking all possible values? That's my suggestion for how I'd tackle the problem. Commented Dec 24, 2012 at 20:31
• Ah, would that mean you would loop all the children first, before going further down the leaves? Commented Dec 24, 2012 at 20:39
• Look at my answer for the looking ahead piece that would be my general approach to solve this now that I have a good idea of what one wants to find, which isn't about looping but recursively calling the function and combining the results. Commented Dec 24, 2012 at 20:40

Recursive solution as follows. Essentially you have to walk the tree in depth first order, returning lists of nodes, and finally building a new tree.

• From a leaf node, return self.
• From a variant node, return a list formed by concatenating the nodes returned by each child, with self inserted at the front.
• At the top level, form a set of tuples that are the Cartesian product of all its child nodes. Then for each tuple create a tree that has self as the head and one tuple as each set of branches; return the list of trees.

It sounds complicated, but it's probably less than 50 lines of Ruby. I'm still not convinced that the question is well formed, but this algorithm will produce the given output.

• thank you for your answer, I'll try to re-formulate the question after solving this problem in code ("to truly understand a problem you first have to solve it"). I am wrapping my head around your solution, and will try to use it in a piece of code later. I'll get back to it. Thanks again. Commented Feb 11, 2014 at 10:00
• @JorritReedijk: a vote would be nice. Commented Feb 11, 2014 at 10:18
• A vote I can not give, I lost my reputation posting something with code. I did accept it as the answer, because this answer gave me the best push in programming a solution Commented Feb 11, 2014 at 14:02
• So I have a recursive function on a node, that returns a list of nodes containing all possibilities on that node: - If the node contains multiple variants to be combined, the returned list contains the cartesion product, - If not then the list contains the tuples, which is the end result So at the top level the tuples are already combined. Commented Feb 11, 2014 at 14:12

I'd be tempted to think there are at least a couple of ways you could describe the solution here:

1. Sets of leaf nodes - As all the parents will be included in each result, it may be simpler to picture a list of lists where you are merely selecting each possible configuration of values. Looking at the example of `((Small box, heavy box),(Standard, Express))` would generate the possibilities which could be done with brute force if nothing else: `((Small box, Standard), (Small box, Express), (Heavy box, Standard), (Heavy box, Express))`

2. Looking ahead - If there are multiple layers to go, then all the nodes will be added but if there is only one more layer to go, then each possibility is to be added. The idea here is to consider how Packaging and Delivery are in each tree yet the leaf nodes are rather uniquely chosen. This could be done recursively looking further down the tree as there are a few special cases to handle like an empty tree and a single node to give a couple of examples. If there are a couple of levels or more then the look ahead idea can be used.

Represent your problem as a grammar:

``````product: packaging delivery
packaging: heavy-box | small-box
delivery: standard | express
``````

This is easy to extend to a third level:

``````product: packaging delivery
packaging: heavy-box | small-box
delivery: standard | express
heavy-box: small | large
``````

With your problem in BNF, all you need is a program that can generate all possible strings accepted by this grammar.

• Thanks! The idea is to eventually end up with a tree with thousands of nodes within dozens of levels, so probably only the nodes with multiple choices would have to be defined in the grammar then to generate the subsets of possibilities Commented Dec 25, 2012 at 5:41

To start with, here is a function to count to total amount of possible new trees. Input is the node at the root of the tree.

``````function CountPossibilities(node)

_result = 0

if node.isvariant then

_result = 0

for each _child in node.childnodes

_result += CountPossibilities(_child)

next

else

_result = 1

for each _child in node.childnodes

_result *= CountPossibilities(_child)

next

end

return _result

end function
``````
• Programmers is tour conceptual questions and answers are expected to explain things. Throwing code dumps instead of explanation is like copying code from IDE to whiteboard: it may look familiar and even sometimes be understandable, but it feels weird... just weird. Whiteboard doesn't have compiler
– gnat
Commented Feb 9, 2014 at 14:32
• I tried to keep any language specifics out of it. Have no clue where to start explaining without some sort of sample. But, I guess this is part of an implementation issue and therefor not suitable for programmers.stackexchange. Commented Feb 9, 2014 at 14:36