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.

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.

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