Enumerating combinations of cells

Question

Say I have 3 cells:

M1={ [1,1,1], [2,2,2] }
M2={ [3,3], [4,4] }
M3={ [5], [6] }

I want to take every element in M1, combine it with every element of M2, combine that with every element of M3, ect.

For the input above, I would like to produce one giant cell like:

[1,1,1],[3,3],[5]
[1,1,1],[3,3],[6]
[1,1,1],[4,4],[5]
[1,1,1],[4,4],[6]
[2,2,2],[3,3],[5]
[2,2,2],[3,3],[6]
[2,2,2],[4,4],[5]
[2,2,2],[4,4],[6]

How can I do this? In general, the number of cells (M1,M2...Mn), and their size, are unknown (and changing).

If the number of cells is unknown, and possibly infinite, a solution might not be possible for practical reasons like insufficient RAM to perform the computation. — Dev-iL, Jul 25 '18 at 19:39
You can use [this answer](https://stackoverflow.com/a/21895344/2586922) with `vectors = { M1 M2 M3 }` — Luis Mendo, Jul 25 '18 at 21:58
@Frank [How does accepting an answer work](https://meta.stackexchange.com/questions/5234/how-does-accepting-an-answer-work) — Jonathan H, Sep 13 '18 at 15:09

score 1 · Answer 1 · answered Jul 25 '18 at 19:47

This function does what you want:

function C = add_permutations(A,B)
% A is a cell array NxK, B is 1xM
% C is a cell array N*M x K+1
N = size(A,1);
A = reshape(A,N,1,[]);
C = cat(3,repmat(A,1,numel(B)),repmat(B,N,1));
C = reshape(C,[],size(C,3));

It creates all combinations of two cell arrays by replicating them in different dimensions, then concatenating along the 3rd dimension and collapsing the first two dimensions. Because we want to repeatedly call it with different cell arrays, input A (NxK) has K matrices in each row, these are the previous combinations. B is a cell vector, each element will be combined with each row of A.

You use it as follows:

M1 = { 'a', 'b', 'c', 'd' }; % These are easier for debugging than OP's input, but cell elements can be anything at all.
M2 = { 1, 2 };
M3 = { 10, 12 };

X = M1.';
X = add_permutations(X,M2);
X = add_permutations(X,M3);

X now contains:

X =

  16×3 cell array

    'a'    [1]    [10]
    'b'    [1]    [10]
    'c'    [1]    [10]
    'd'    [1]    [10]
    'a'    [2]    [10]
    'b'    [2]    [10]
    'c'    [2]    [10]
    'd'    [2]    [10]
    'a'    [1]    [12]
    'b'    [1]    [12]
    'c'    [1]    [12]
    'd'    [1]    [12]
    'a'    [2]    [12]
    'b'    [2]    [12]
    'c'    [2]    [12]
    'd'    [2]    [12]

Jonathan H · Accepted Answer · 2018-07-26T21:45:36.817

That's not a permutation, it's an enumeration: you have 3 symbols, each with 2 possible values, and you are simply enumerating all possible "numbers". You can think about it the same way as if you were counting binary numbers with 3 digits.

In this case, one way to enumerate all these possibilities is with ndgrid. If M1 has n1 elements, M2 has n2 elements, etc:

n1 = numel(M1);
n2 = numel(M2);
n3 = numel(M3);

[a,b,c] = ndgrid(1:n1, 1:n2, 1:n3);

Here a,b,c are each 3-dimensional array, which represent the "grid" of combinations. Obviously you don't need that, so you can vectorise them, and use them to create combinations of the various elements in M1, M2, M3, like so

vertcat( M1(a(:)), M2(b(:)), M3(c(:)) )

If you are interested in generalising this for any number of Ms, this can also be done, but keep in mind that these "grids" are growing very fast as you increase their dimensionality.

Note: vertcat stands for "vertical concatenation", the reason it is vertical and not horizontal is because the result of M1(a(:)) is a row-shaped cell, even though a(:) is a column vector. That's just indexing headache, but you can simply transpose the result if you want it Nx3.

Enumerating combinations of cells

2 Answers2