Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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)?

share|improve this question
    
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? –  JB King Dec 24 '12 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 :) –  Jorrit Reedijk Dec 24 '12 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. –  JB King Dec 24 '12 at 20:31
    
Ah, would that mean you would loop all the children first, before going further down the leaves? –  Jorrit Reedijk Dec 24 '12 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. –  JB King Dec 24 '12 at 20:40

4 Answers 4

up vote 0 down vote accepted

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.

share|improve this answer
    
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. –  Jorrit Reedijk Feb 11 at 10:00
    
@JorritReedijk: a vote would be nice. –  david.pfx Feb 11 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 –  Jorrit Reedijk Feb 11 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. –  Jorrit Reedijk Feb 11 at 14:12

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
share|improve this answer
    
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 Feb 9 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. –  Jorrit Reedijk Feb 9 at 14:36

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.

share|improve this answer
    
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 –  Jorrit Reedijk Dec 25 '12 at 5:41

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.