Too many for loops, how to approach rearranging arrays problem differently?

Hi all!

I have the following issue: I need to perform a function to different combinations of elements of arrays, say a and b. To simplify, say that I need to sum every combination of the sums of the elements of a(1:2),...,a(1:10), a(2:3),...,a(2:10), and every combination of the sums of the elements of b(1:2),...,b(1:10),b(2:3),...,b(2:10).

The way I approached the problem is by building a function that gets fed with an array and a window of its values (f1), and then a second function that loops the first one using every possible starting point of the array (f2).

Then, I run 4 different loops, to take every possible combination of windows i (for vector a) and k (for vector b), and positions j (for vector a) and l (for vector b).

Here the script and functions.

Now I have a problem though: since I am using 4 loops, the code runs extremely slowly if a and b are too large.

I know it's a very generic question, but is there any other way I can approach the problem that would allow me to cut time?

a=1:10;
b=10:19;
aa=f22(a);
bb=f22(b);
for i=1:length(aa)
    for j=1:length(bb)
        for k=1:length(aa{i})
            for l=1:length(bb{j})
                solutions(i,j,k,l)=sum(aa{i}{1,k})+sum(bb{j}{1,l});
            end
        end
    end
end

function Y=f1(X,W)
for i=1:length(X)-W
    Y{i}=X(i:W+i);
end
end

function M=f2(Y)
for i=1:length(Y)-1
    M{i}=f1(Y,i);
end
end

[Jan]

What is f22?

[Happy_Shovel]

sorry, it's a typo, I meant f2,

function M=f2(Y)

for i=1:length(Y)-1

M{:,i}=f11(Y,i);

end

end

Answer 1

[Jan]

Pre-allocate the output and avoid repeated calculations:

a  = 1:50;
b  = 10:50;

tic
aa = f2(a);
bb = f2(b);
for i = 1:length(aa)
    for j = 1:length(bb)
        for k = 1:length(aa{i})
            for l = 1:length(bb{j})
                solutions(i,j,k,l) = sum(aa{i}{1,k}) + sum(bb{j}{1,l});
            end
        end
    end
end
toc

Elapsed time is 1.626255 seconds.

tic
aa = f2P(a);
bb = f2P(b);
% solutions2 = zeros(length(aa), length(bb), length(aa), length(bb));
solutions2 = zeros(length(bb), length(aa), length(bb), length(aa));
for i = 1:length(aa)
    aai = aa{i};
    for j = 1:length(bb)
        bbj = bb{j};
        for k = 1:length(aai)
            s1 = sum(aai{k});
            for l = 1:length(bbj)
                solutions2(l,k,j,i) = s1 + sum(bbj{l});
            end
        end
    end
end
solutions2 = permute(solutions2, [4,3,2,1]);
toc

Elapsed time is 0.191000 seconds.

isequal(solutions, solutions2)

ans = logical
   1

function Y = f1(X,W)
for i = 1:length(X)-W
    Y{i} = X(i:W+i);
end
end
function M = f2(Y)
for i = 1:length(Y)-1
    M{i} = f1(Y,i);
end
end

function Y = f1P(X,W)  % With pre-allocation
Y = cell(1, length(X) - W);
for i = 1:length(X)-W
    Y{i} = X(i:W+i);
end
end
function M = f2P(Y)  % With pre-allocation
M = cell(1, length(Y) - 1);
for i = 1:length(Y)-1
    M{i} = f1(Y,i);
end
end

Maybe it is more efficient to collect the data columnwise:

solutions2 = zeros(length(bb), length(aa), length(bb), length(aa));
...
               solutions2(l,k,j,i) = s1 + sum(bbj{l});
...
solutions2 = permute(solutions2, [4,3,2,1]);

Please measure the timings locally on your computer.

Answer 2

[David Hill]

a=1:10;
b=10:19;
sa=0;sb=0;
for k=2:numel(a)
    sa=sa+sum(nchoosek(a,k),'all');
    sb=sb+sum(nchoosek(b,k),'all');
end