Elements processing in array

If array A=[ b c ], I want to create value [b+c -b+c b-c -b-c]

or A=[ b c d ], then output should be [ b+c+d b+c-d b-c+d b-c-d -b+c+d -b+c-d -b-c+d -b-c-d ]

Is there any function in MATLAB that can easily solve my problem ? Thanks.

Answer 1

[Guillaume]

You basically want the sum of the n-ary product of the +/- sets of each element of your array. That can be done easily with ndgrid:

A = [1 3 8 2];  %demo data;
sets = num2cell([A; -A], 1);  %split into sets of +/- values
nprod = cell(1, numel(A));  %create destination for n-ary product
[nprod{:}] = ndgrid(sets{:});  %calculate n-ary product
nprod = reshape(cat(numel(A)+1, nprod{:}), [], numel(A)); %concatenate into one matrix and reshape. Each row is one of the possible combination
sumnprod = sum(nprod, 2)  %wanted result

[Lee Lee]

OK,thanks a lot.

[Jan]

+1: This is efficient for larg inputs - and as usual for code concerning permutations, "large" means 20 elements already.

Answer 2

[Jan]

With http://www.mathworks.com/matlabcentral/fileexchange/26242-vchoosekro:

n = numel(A);
M = VChooseKRO([-1, 1], n) * A(:);

Timings: See comment.

And if single precision is enough, this is 33% faster for an [1 x 20] input:

n = numel(A);
M = VChooseKRO(single([-1, 1]), n) * A(:);

Answer 3

[Jan]

n = numel(A);
M = (1 - 2 * (dec2bin(0:2^n-1) - '0')) * A(:);

[EDITED, parenthesis inserted]

[Guillaume]

That is indeed shorter than my answer and possibly will fall over later than ndgrid on larger arrays. However, it's probably slower due to number - string conversions.

[Jan]

@Guillaume: I know, I detest dec2bin in my code and use it in the forum only. I productive codes I'd use:

n = numel(A);
s = rem(floor((0:2^n-1).' * pow2((1-n):0)), 2);
M = (1 - 2 * s) * A(:));

Before speculating about speed, let's measure it:

A   = 1:5;
rep = 10000;  % Repetitions for accurate timings

tic;
for k = 1:rep
  sets = num2cell([A; -A], 1);
  nprod = cell(1, numel(A));
  [nprod{:}] = ndgrid(sets{:});
  nprod = reshape(cat(numel(A)+1, nprod{:}), [], numel(A));
  sumnprod = sum(nprod, 2);
end
toc

tic;
for k = 1:rep
  n = numel(A);
  M = (1 - 2 * (dec2bin(0:2^n-1) - '0')) * A(:);
end
toc

tic;
for k = 1:rep
  n = numel(A);
  s = rem(floor((0:2^n-1).' * pow2((1-n):0)), 2);
  M = (1 - 2 * s) * A(:);
end
toc

tic;
for k = 1:rep
  M = VChooseKRO([-1, 1], numel(A)) * A(:);
end
toc

R2016b/64, Win7:

 Elapsed time is 1.799392 seconds.    Guillaume
 Elapsed time is 0.355071 seconds.    DEC2BIN
 Elapsed time is 0.278210 seconds.    my_DEC2BIN
 Elapsed time is 0.078271 seconds.    VChooseKRO

And now with a larger input:

A   = 1:20;
rep = 2;

 Elapsed time is 1.007342 seconds.    Guillaume
 Elapsed time is 3.261605 seconds.    DEC2BIN
 Elapsed time is 2.929411 seconds.    my_DEC2BIN
 Elapsed time is 0.468315 seconds.    VChooseKRO

Conclusion: The multiplication with the binary matrix is fast for small arrays and slow for large arrays. The conversion to CHAR and back has some overhead. Creating large temporary array in a DEC2BIN style is a bad idea. But with an efficient creation of the [1, -1] matrix the computations are faster than the cell approach. But therefore it is required to compile a C-Mex function. Therefore is pure Matlab is wanted, Guillaume's method is better - except a user needs millions of results for short input vectors.