1
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ What's the context in which you encountered this problem? Can you edit the question to credit the source? What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercise/program-contest-style problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W.♦ Apr 8 '18 at 3:04
  • $\begingroup$ What if some groups are intersected? Could you please give an example? $\endgroup$ – xskxzr Apr 8 '18 at 7:15
1
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's an interesting observation. Let me try to prove this. If it works, my implementation will become so concise! $\endgroup$ – TheBlueNotebook Apr 8 '18 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.