MATLAB: Algorithm to find out combinations of known vectors for resultant vector

complex numbervector

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.

Best Answer

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)
Related Question