All possible combinations from a matrix such that sum of all numbers equals to a fixed value

Hi. Suppose I have Q vectors as follows:

    A_1 = [x_1,x_2,...,x_m];
    A_2 = [y_1,y_2,...,y_n];
    .
    .
    .
    A_Q = [z_1,z_2,...,z_q];

Basically, m,n,q are positive integers and not necessarily equivalent. Each vector element x,y,z is a number between (0,1). One possible combination of these vectors can be:

    B_1 = [x_1,y_1,...,z_1];

In each combination, only one element of each vector should be included. Therefore, we can have m*n*q different combinations. Now, I want to find those combinations such that mean of their elements equals to a specific number W, i.e., mean(B_1)=W. Note that W is a number between (0,1). An inefficient way is to compute all permutations and then compare W with the mean of their elements. However, as Q,m,n,q increase, the computer (MATLAB) can't handle it, which is obvious.

Would you please help me find an efficient approach to solve this problem in a reasonable time?

One can say that there may not be a vector, where the mean of its elements equals to W. Yes, that's true. Then, is it possible to find combinations such that the mean of their elements is between (W-T,W+T), where T is between (0,1)?

Many thanks in advance.

Answer 1

[John D'Errico]

You are in trouble for a variety of reasons.

This is a variation of a classical partitions problem, usually described in terms of integers that sum to a given value. Usually, the problem is in terms of a sum of the integers 1:n.

That the problem is phrased as a mean is not really relevant. We can just look at it as the sum of Q elements from these sets such that they sum to Q*W.

As Q increases, the number of such solutions, increases pretty rapidly. Computing them all will take much time.

Next, the sum of any set of floating point numbers will never be exactly any value. You need to allow a tolerance. Of course, that makes the problem more difficult yet.

How should you solve it? Recursion is the simple solution. Here a loop will suffice. Your target sum must live in the interval

[Q*W-tol,Q*W+tol]

To generate all possible possible combinations that yield the desired sum, just set up a loop. Consider all elements from the CELL array A{1}.

Note that I will not allow you to phrase this in terms of vectors A_1, A_2, etc. Sorry, but that is a foolish thing to do. Use a cell array to contain ALL of your vectors in one array.

If any of those elements are less than Q*W+tol, then they are potential elements of one valid partition. Then consider which elements of A{2} might fall in the sum.

All of these potential combinations will grow rapidly. While computable, it will take time.

Is there a better way? Perhaps.