0

I have problem which requires me to compare all children of two nodes of general tree. Each parent can have multiple children, for each comparison I have to get best possible combination. For example if I wanted to compare nodes B and F possible combinations of children are: C:G, C:H, D:G, D:H, E:G, E:H.

Example tree

For each pair I have result data that is stored in arrays: 

[[2,0],    [[C:G,C:H],
 [3,5],  = [D:G,D:H],
 [2,3]]    [E:G,E:H]]

I tried brute force algorithm similar to this one: https://www.geeksforgeeks.org/combinations-from-n-arrays-picking-one-element-from-each-array/ but this solution allows best combination to be one, where one node is paired multiple times with node from other tree.

In case of comparison 3x3 nodes possible solutions are:

Matrix of possible pairs values:
[[1,0,1],
 [0,2,1],
 [1,1,0]]
Possible combinations with results:
[0,0],[1,1],[2,2] = 3
[0,0],[1,2],[2,1] = 3
[0,1],[1,0],[2,2] = 2
[0,1],[1,2],[2,0] = 0
[0,2],[1,1],[2,0] = 4
[0,2],[1,0],[2,1] = 2

I wonder should I use that matrix and if so, how to implement algorithm. I'm writing in C++ but it is part of uni assignment so I don't want ready code, just pseudo-code solution, or pointers to look in right direction. I cannot use library algorithm, or others. I have to implement solution myself. I was thinking about recursive function that passes all cells in column that were visited, but I think there is easier way to do that. I can use brute force approach, so I'm looking to calculate all possible combinations and pick best.

Hrzug
  • 21
  • 3
  • 1
    That site you linked to is notorious for bad code. The example you linked to has memory leaks. It seems the original author of that code is not aware of the purpose of `std::vector`, thus the leaks appear. – PaulMcKenzie May 18 '20 at 14:10
  • Does this answer your question? [Generate all combinations from multiple lists](https://stackoverflow.com/questions/17192796/generate-all-combinations-from-multiple-lists) – scohe001 May 18 '20 at 14:12
  • @scohe001 Not really, He was looking for all possible combinations, including repetition. – Hrzug May 18 '20 at 14:18
  • @Hrzug *I cannot use library algorithm, or others* -- If you could use a "library algorithm or others", what would you choose? Whatever that is, implement that choice yourself. You could even prototype a solution quickly by using the STL algorithm(s), and when the program works, go back and see how to implement what you used. – PaulMcKenzie May 18 '20 at 14:39

0 Answers0