How to get started with multi-level pairwise combinations


Let’s say we have 4 ranks: 1-4

Every rank has a set of unique nodes, each pair of same-rank nodes can be combined to create a node of a rank 1 level higher, in any number of combinations:

1-A + 1-B = 2-C 1-A + 1-A = 2-B 1-A + 1-C = 2-C 1-B + 1-C = 2-A 

These combinations are deterministic, we have a lookup table to get any pair-result combination and the result is not unique.

Once combined, they cannot be used again. So in the example above, we can do:

We have [1-A, 1-A, 1-B, 1-C] We perform 1-A + 1-A = 2-B Now the only nodes we have left are 1-B and 1-C = 2-A 

Rank 4’s cannot combine, they are the final rank.

Let’s say I have a random set of Rank 1, 2, and 3 nodes.

I would like to build a “planner” where the user can see paths to Rank 4 and decide which nodes to use.

I have a simple algorithm where I calculate all combinations of each rank, get the results and pass it up to the next rank to perform the same algorithm:

1. starting set = [1-A, 1-A, 1-B, 1-C, 2-A] 2. split into buckets: [1-A, 1-A, 1-B, 1-C] and [2-A] 3. go through Rank 1, create all combinations: C(4,2) = 6 4. add the resulting 6 to the single node of Rank 2 for a total of n = 7 5. repeat step 3-4 for Rank 2: C(n,r) = 21 6. repeat step 3-4 for Rank 3: C(n,r) = 210 

The problem here is that with a small set of 5 starting nodes, the possibilities exponentially grow and with 210 possible Rank 4 paths, will get very noisy.

Since any two nodes can only be used once, with a starting set of length 5, if I choose a random 2 to merge, this will remove pretty much all the later paths.

How do I somehow reduce the noise? I’m not sure if I should be looking at Graph Theory, some other simple algorithm, or do a grouping/counting of unique nodes.