On Thu, Jun 30, 2011 at 2:18 PM, Przemek Klosowski
<address@hidden> wrote:
(snip)
Specifically, I had 75 boards of lengths ranging from 25cm to 195cm,
and I needed 319.8 cm runs. I had my kid measure the boards to within 1mm and read it into an Octave variable 'a'. I then calculated the sums of all combinations of four boards---the 2 and 3 plank combinations are also included because I added two 'virtual' planks of length 0 to the set. I calculated only the 'upper triangular' combinations, of course:
tic;
m=length(a); z=1;
sz=m*(m-1)*(m-2)*(m-3);ind=zeros(sz,4);sum=zeros(sz);
for i=1:m;
for j=1:i-1;
for k=1:j-1;
for l=1:k-1;
ind(z,1:4)=[i,j,k,l];
sum(z)=a(i)+a(j)+a(k)+a(l);
z++;
end ;
end;
end;
end ;
toc;
So, is there a vectorized way of writing this? Some sort of 'tensor' operation, I guess...
I have no expertise in combinatorial optimization, so I'll just help with your brute force method.
I think the nchoosek() function is what you want. If you give it a vector as the first argument (e.g., nchoosek(v,k)), it produces an array where each row is a combination of k elements of v. I don't believe it repeats. So, to implement...
% plank lengths
n = 75;
a = rand(n,1)
% Produce all combinations at once.
combs = nchoosek(1:n,4);