Generate all possible combinations of the elements of some vectors (Cartesian product)

Question

I would like to generate all the possible combinations of the elements of a given number of vectors.

For example, for [1 2], [1 2] and [4 5] I want to generate the elements:

[1 1 4; 1 1 5; 1 2 4; 1 2 5; 2 1 4; 2 1 5; 2 2 4; 2 2 5]

The problem is that I don't know the number of vectors for which I need to calculate the combinations. There might be 3 as in this case, or there may be 10, and I need a generalization. Can you please help me to this in MATLAB? Is there already a predefined function that can do this task?

Hitt

what you are looking for is called the 'cartesian product' of the vectors. You may have some luck googling for that. – Eben

Answer 1

Try ALLCOMB function at FileExchange.

If you store you vectors in a cell array, you can run it like this:

a = {[1 2], [1 2], [4 5]};
allcomb(a{:})
ans =

     1     1     4
     1     1     5
     1     2     4
     1     2     5
     2     1     4
     2     1     5
     2     2     4
     2     2     5

Hearty

Note that ALLCOMB uses NDGRID in essentially the same way as in Amro's answer, with error-proofing on top. – Foal

Answer 2

Consider this solution using the NDGRID function:

sets = {[1 2], [1 2], [4 5]};
[x y z] = ndgrid(sets{:});
cartProd = [x(:) y(:) z(:)];

cartProd =
     1     1     4
     2     1     4
     1     2     4
     2     2     4
     1     1     5
     2     1     5
     1     2     5
     2     2     5

Or if you want a general solution for any number of sets (without having to create the variables manually), use this function definition:

function result = cartesianProduct(sets)
    c = cell(1, numel(sets));
    [c{:}] = ndgrid( sets{:} );
    result = cell2mat( cellfun(@(v)v(:), c, 'UniformOutput',false) );
end

---

Note that if you prefer, you can sort the results:

cartProd = sortrows(cartProd, 1:numel(sets));

Also, the code above does not check if the sets have no duplicate values (ex: {[1 1] [1 2] [4 5]}). Add this one line if you want to:

sets = cellfun(@unique, sets, 'UniformOutput',false);

Mellie

Answer 3

This late answers provides two additional solutions, where the second is the solution (in my opinion) and an improvement on Amro's answer solution with ndgrid by applying MATLAB's powerful comma-separated lists instead of cell arrays for high performance,

1. If you have the Neural Network Toolbox: use combvec
2. If you do not have the toolbox, as is usually the case: below is another way to generalize the Cartesian product for any number of sets.

Just as Amro did in his answer, the comma-separated lists syntax (v{:}) supplies both the inputs and outputs of ndgrid. The difference (fourth line) is that it avoids cellfun and cell2mat by applying comma-separated lists, again, now as the inputs to cat:

N = numel(a);
v = cell(N,1);
[v{:}] = ndgrid(a{:});
res = reshape(cat(N+1,v{:}),[],N);

The use of cat and reshape cuts execution time almost in half. This approach was demonstrated in my answer to an different question, and more formally by Luis Mendo.

Mechanics

THIS is the way to go in my opinion. Noticed that it can easily be extended to get all the permutation of length m for a vector of length n with: [v{1:m}] = ndgrid(1:n); and res = reshape(cat(m+1,v{:}),[],m) – Thermos

Answer 4

Since MATLAB 2023a you can use the combinations function, which supports vectors, matrices, cell arrays, and mixtures thereof:

>> combinations([1 2], [1 2], [4 5])

ans =

  8×3 table

    Var1    Var2    Var3
    ____    ____    ____

     1       1       4  
     1       1       5  
     1       2       4  
     1       2       5  
     2       1       4  
     2       1       5  
     2       2       4  
     2       2       5  

The output is in the form of a table, which supports mixed types. If your outputs need only a single type, you can convert the output to a matrix using table2array:

>> table2array(combinations([1 2], [1 2], [4 5]))

ans =

     1     1     4
     1     1     5
     1     2     4
     1     2     5
     2     1     4
     2     1     5
     2     2     4
     2     2     5

For what it's worth, I have written a shim that emulates the behaviour of combinations in older versions of MATLAB (down to version 2013b), including support for mixed types:

function grid = combinations(varargin)
    grid = cell(nargin, 1);
    [grid{:}] = ndgrid(varargin{:});

    combos = cellfun(@(it) it(:), grid, 'UniformOutput', false)';
    combos = table(combos{:});
end

Hudis

Answer 5

we can also use the 'combvec' instruction in matlab

    no_inp=3 % number of inputs we want...in this case we have 3 inputs                  
    a=[1 2 3]
    b=[1 2 3]
    c=[1 2 3]

    pre_final=combvec(c,b,a)';
    final=zeros(size(pre_final));

    for i=1:no_inp
    final(:,i)=pre_final(:,no_inp-i+1);
    end
    final 

Hope it helps. Good luck.

Ox