algorithm to find out combinations of known vectors for resultant vector

Hi, i have a lists of vector (actually in complex number) like v1 = [1, 2] v2 = [2, 3] v3 = [1, 1] v4 = [5, 10] ... and i am looking at the resultant vector, says, [8 , 13] any idea what straight forward algorithm I should use to find out the combinations of vectors which can result in [8, 13] in this case?

i understand there will be many possible combinations that i would limit them by scores beforehand.

[Stephen23]

"i have a lists of vector ... like v1 = [1, 2] v2 = [2, 3] v3 = [1, 1] v4 = [5, 10] ..."

And that is the start of your problems right there. Do NOT try to magically access variables names, unless you want to force yourself to write slow, buggy, complex code that is hard to debug. Your code would be much simpler, neater, and more efficient if you simply stored your data in one array and used indexing.

Read this to know why your approach is slow, buggy, complex, and insecure:

https://www.mathworks.com/matlabcentral/answers/304528-tutorial-why-variables-should-not-be-named-dynamically-eval

Whatever method you use to create/load so many variables can be trivially altered to use indexing and one variable. Note how the first step of KSSV's answer is to put all of your vectors into one array. You should do the same.

[Walter Roberson]

Is this about using linear multiples, or is each item to be either used or unused ?

[Omega Wea]

Thanks for the advice. i have not written any code yet since i wish to first put things together.

My question was just an example. Because my data consists of numerous complex number and the target is also an complex number.

And the target is the sum of these complex number in my data.

[Guillaume]

You haven't answered Walter's question: Are you allowed to reuse the same vector several time for the sum? Or is the option for each just used/not used?

[Torsten]

Is this the problem you are dealing with ?

https://en.wikipedia.org/wiki/Subset_sum_problem

Best wishes

Torsten.

[Walter Roberson]

Are the values complex integers or are they complex floating point that might have fractions?

[Omega Wea]

i think at this stage, just treat them as used/not used and complex integers for now.

Answer 1

[Guillaume]

Assuming used/not used, this is fairly easy when the size of the set is reasonably small (~ 20 elements max) as you can just try all combinations:

values = [1 + 2i;
          2 + 3i;
          1 + 1i;
          5 + 10i;
          1 + 0i;
          3 + 3i];  %demo data
target = 8 + 13i;

combs = dec2bin(0:2^numel(values)-1).' - '0';
ishit = sum(values .* combs) == target;
validcombs = logical(combs(:, ishit))  %each column is a valid combination of vector. true says to use that vector

If you'd rather have a list of indices:

validcombs = cellfun(@find, num2cell(validcombs, 1), 'UniformOutput', false)

[Omega Wea]

seem to me there is some issue in this line:

sum(values .* combs)

Do you think this is what you meant?

ishit = sum(bsxfun(@times,combs,values(:))) == target;

[Guillaume]

Well, yes if you're on a version earlier than R2016b, then you have to use bsxfun exactly as you've written. With the implicit expansion introduced in R2016b, the two are equivalent.

[Walter Roberson]

Implicit expansion was introduced in R2016b

[Omega Wea]

i wish to follow up with this question. What if the values are complex floating point that might have fractions? and i would allow amount of uncertainty,say +/- 2 on both axis.

[Guillaume]

As long as the set is reasonably small so that you can calculate all the combinations at once, then it's the same algorithm. The only difference is the hit test, which you'd change to

ishit = abs(sum(values .* combs) - target) <= yourtolerance;

or, prior to R2016b:

ishit = abs(sum(bsxfun(@times, values, combs)) - target) <= yourtolerance;

[Omega Wea]

great thanks. what would u suggest if the set if large instead? i think the data might grow in future. is it only the process time be longer? or matlab cannot handle more than that?

[Guillaume]

The number of combinations is 2^(size of set). Above some size calculating them all will take too much memory/time.

If the set is too big, then you'll have to use a cleverer approach, possibly something out of the optimisation toolbox, with which I'm completely unfamiliar.