I am trying to come up with an efficient algorithm to solve the following problem but not able to design anything nice. I am encountering this problem for a project I am pursuing. Following is an abstracted version of the problem so that I don't confuse anyone with the specifics.
The problem is like this:
I have a list of groups. each group might have an arbitrary number of elements with some weight in it. A valid vector comprises of exactly one member from each group and has members from each group in the list. The weight of a vector is the product of weights of the members in the vector. I want to find the sum of weights of all valid vectors.
for example:
Group 1: Member 1, Member 2
Group 2: Member 3
Valid Vector 1: Member 1, Member 3
Valid Vector 2: Member 2, Member 3
We need to find: (Member 1 * Member 3) + (Member 2 * Member 3)
The groups don't intersect. Which means a member can belong to only one group. What I am doing currently is a brute force like solution, where I start with creating a global list and populating it with the members of group 1. I then go to the next group (group 2) and extend the global list by multiplying each member of group 2 with each member in the global list. Thus completely replacing global list with all pairs of members from group 1 and group 2. In this manner, I keep extending the global list till I have processed all groups.