3

I have a 1-dimensional cell array Z. Each cell of Z contains a vector. For example:

Z{1} = [1 2];
Z{2} = [3 4 5];
Z{3} = [6];
...
Z{length(Z)} = [10 11 12 13];

The sizes of those vectors are all different. What I want to do is to compare the sum of functions values of all possible combinations with one element from each Z{i}. That is I want to compare all the following combinations:

func(1) + func(3) + func(6) + ...
func(1) + func(4) + func(6) + ...
func(1) + func(5) + func(6) + ...
func(2) + func(3) + func(6) + ...
func(2) + func(4) + func(6) + ...
func(2) + func(5) + func(6) + ...
...
...

and I want to know which combination yields the maximum.

How can I smartly do this? The smarter, the better. But I am also looking for any working code. The problem size will be small.

Note: The actual values used in this example, 1, 2, 3, 4, 5, 6, ... are just examples. They don't have any specific pattern.

Chang
  • 846
  • 10
  • 23

1 Answers1

2

Consider the following solution, it has a cycle but it does what you want linearly in time instead of exponentially.

Iteratively, the algorithm runs throughout all the rows of Z making all the possible paths among the entries of the row Z{i}. Nonetheless, each entry is parsed just once, thus you save complexity. 

 N = 3;

 Z = cell(1,N);

 Z{1} = [1 2];
 Z{2} = [3 4 5];
 Z{3} = [6];

 f = @(x) x.^2;  %% Test function



disp('init')
res = arrayfun(f,(Z{1}))     %% Init step. Image of Z{1}
for i = 2 : N
   disp(i)      %% just to have an idea of where you are in the process
   disp(res)

   t = bsxfun(@plus,res,arrayfun(f,(Z{i}))')  %In a tensor way you build all
                                              %the possible sum of the res and f(Z{i})
                                              %making all paths.
   res = reshape(t,1,[])                      %You put the tensor sum on a single
                                              %row to be able to iterate.  
   disp('END step-------')
end

test with squares

res =

46    53    62    49    56    65

for instance 46 = 1^2 + 3^2 + 6^2, 49 = 2^2 + 3^2 + 6^2...

So far I am not sure you can avoid cycles completely. What I do here is dynamically constructing the solution adding one element of your cell at every iteration.

Tensor summation technique (t = bsxfun(@plus,res,arrayfun(f,(Z{i}))')) from this answer.

Community
  • 1
  • 1
Acorbe
  • 8,367
  • 5
  • 37
  • 66
  • In this case, what I am looking for is: [1 3 6]^2, [1 4 6]^2, [1 5 6]^2, [2 3 6]^2, [2 4 6]^2, [2 5 6]^2. I think you did [1 2]^2, [3 4 5]^2, [6]^2. – Chang Nov 17 '12 at 18:00
  • Got you, every possible combination of those. OK – Acorbe Nov 17 '12 at 18:02
  • @Chang, You may want to consider the answer now. – Acorbe Nov 17 '12 at 18:29
  • @Chang, I added some comments. – Acorbe Nov 17 '12 at 18:42
  • Thanks a lot! However, how do I know what combination yields the maximum of `res`? – Chang Nov 17 '12 at 18:48
  • That is not hard, find the index of `max(res)`. From such index and knowing all the `length(Z{i})` you can easily build the path. Just understand what the algorithm I suggested you does, and you will easily find the solution you look for. – Acorbe Nov 17 '12 at 18:51
  • @Chang, basically it depends on how `reshape` reshapes the `2xK` matrix to a `1x2K` vector. – Acorbe Nov 17 '12 at 18:53