Efficient way to generate all possible combinations of elements in 2 arrays

Question

I have an array A=[1,2] and B=[5,6]
I want to generate an array C=[1*1,2*2,5*5,6*6,1*2,1*5,1*6,2*5,2*6,5*6]
That is all the possible combinations (ab is equal to ba and hence only 1 of them should be on the resultant C array).

Does matlab have an inbuilt function I can use to achieve this?
Can you help me?

What if you have A=[2,4] B=[3,6] - should 12 appear twice (3*4,6*2) or only once? — amit, Mar 23 '15 at 08:00
How does *2 arrays* come into play here? It seems it doesn't matter which elements are in which array. It should be the same as choosing 2 elements from `[A,B]`. — knedlsepp, Mar 26 '15 at 13:12

score 3 · Accepted Answer · edited May 23 '17 at 12:22

Two approaches with bsxfun could be suggested here.

Approach #1

%// Form a concatenated array
AB = [A(:) ; B(:)]

%// Get pairwise multiplications between all elements
allvals = bsxfun(@times,AB,AB.') %//'

%// Discard the repeated ones for the final output
C = allvals(bsxfun(@le,[1:numel(AB)]',1:numel(AB)))

Approach #2

%// Form a concatenated array
AB = [A(:) ; B(:)]

%// Get "non-repeated" pairwise indices
[Y,X] = find(bsxfun(@le,[1:numel(AB)]',1:numel(AB))) %//'

%// Elementwise multiplications across all such pairs for final output
C = AB(X).*AB(Y)

The second one is based on Fastest solution to list all pairs of n integers and is less memory hungry than the first approach.

score 2 · Answer 2 · answered Mar 23 '15 at 10:46

2

An alternative is to use pdist (from the Statistics Toolbox) with an anonymous function:

AB = [A(:); B(:)];
C = [AB.'.^2 pdist(AB, @(x,y) x*y)];

answered Mar 23 '15 at 10:46

Luis Mendo

109,078
12
70
142

Good thinking on this! Did some quick tests and this one is the fastest for really large arrays! – Divakar Mar 23 '15 at 16:52
@Divakar Thanks! In recent versions of Matlab `pdist` uses a mex file to do the actual computations; that must be (part of) the reason – Luis Mendo Mar 23 '15 at 21:07
1

Well, my tests state that my Approach #1 `bsxfun` performs really well until numel(A) is `2000` i.e. numel(AB) is `4000`, after which I am guessing the heavy memory requirements of `bsxfun` kicks in and then `pdist` starts to shine thereafter. Not seeing a clear winner! – Divakar Mar 23 '15 at 21:14

score 1 · Answer 3 · edited Mar 23 '15 at 10:36

1

Try the following code:

%merge
AB = [A(:) ; B(:)]
%multiply to get all combinations
C=AB*AB'
%delete everything below the first diagonal
C=C(triu(true(numel(AB))));

edited Mar 23 '15 at 10:36

kenorb

137,499
74
643
694

answered Mar 23 '15 at 09:28

Daniel

36,282
3
33
67

score 0 · Answer 4 · answered Mar 26 '15 at 13:18

0

It doesn't add much to the question that you are using two vectors. You just want the product of every n choose 2 combination of the concatenation x = [A(:); B(:)].

prod(x(nchoosek(1:numel(x), 2)), 2)

answered Mar 26 '15 at 13:18

knedlsepp

5,933
3
17
40

Efficient way to generate all possible combinations of elements in 2 arrays

4 Answers4