Algorithm for this problem on generating all permutations

Question

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.

Answer 1

Suppose that there are $n$ groups, that group $i$ has the $m_i$ elements $x_{ij}$. It is a nice exercise to show that the sum of weights of all valid vectors is $$ \prod_{i=1}^n \sum_{j=1}^{m_i} x_{ij}. $$ (In you example, you can factor your formula as (Member 1 + Member 2) * Member 3.)