Combinations of values of array of vectors (of different lengths) but ONLY in order the vectors appear in the array?

Hi, I'm trying to transcribe protein letters to DNA codons. I have a single row array that looks like:

[N1 N2 N3 N4 ...]

Each vector looks like:

N1 = {'UUU' 'UUG' 'UUC'} or
N2 = {'AUU' 'AUG' 'AUC' 'AAU' 'AAG'}
(number of cells can vary from 1 to 6)

I want every combination of the values of these vectors BUT only in the order they appear in the main [N1 N2] vector. For example, 'UUU AUU' and "UUU AUG' are desirable but 'AUU UUU' and 'AUG UUU' are NOT.

Also every combination must contain a value from each vector. So if the array has 20 'N' vectors then each combination needs 20 'three letter' strings.

I'm not much of a coder and I've ended up in a useless mess of nested loops. I think this is a problem for recursion but I'm stuck :(

Your help and time are greatly appreciated! :) Also please let me know if I can clarify anything.

edit: put examples in matlab syntax

[Guillaume]

Can you please use valid matlab syntax for your examples. It would be much easier to understand what your inputs are.

For example is the array actually a cell array of the form

{vector1, vector2, vector3, ...}
%or maybe
{vector1; vector2; vector3; ...}

or something else? It certainly can't be a matrix according to your description.

What are the vectors made of. Are they again cell arrays of something (char arrays?) like so:

vector1 = {'UUU', 'UUG', 'UUC'};

or something else entirely?

[David Goodmanson]

For 20 N-vectors of average length 3, there are about 3.5 x 10^9 unique combinations. So this could get to be pretty memory intensive.

[Evan Meichtry]

Guillaume, I tried to fix the syntax. Hopefully it is clearer now. To answer your question everything is a single row.

David, that's a lot of combinations!! However, I only want combinations N cell arrays while keeping the actual N arrays in the same order, does that make sense? It's difficult to put into words. I hope that reduces the unique combinations enough.

[Guillaume]

Evan, yes it is a lot clearer thanks. However, I assume that the main array is actually {N1 N2 N3 N4 ...} not [N1 N2 N3 N4 ...], otherwise, once you've concatenated the Ns, there's no way to know which N the char arrays came from.

David is completely right. Just picking one of 3 elements from 20 consecutive vectors in order is 3^20 = ~3.5e9 combinations. You will need at least 13 GB of memory just to store all combinations of indices Extend that to 6 elements per vector and that's ~3.5e15 combinations and 13 PB (PetaBytes) of memory.

You probably need to review your approach to the problem.

Answer 1

[Chaya N]

If I understand your question right, I think that your problem is one of creating unique combinations out of unequal length vectors. Perhaps you should look up the combvec function.

As a sample, when I run the following code snippet:

 x = [1,2];
 y = [4,5,6];
 z = [8,9];
 combvec(x,y,z)

I get the following answer (read column-wise of course)

 ans =

     1     2     1     2     1     2     1     2     1     2     1     2
     4     4     5     5     6     6     4     4     5     5     6     6
     8     8     8     8     8     8     9     9     9     9     9     9

To me this sounds like exactly what you require.

Good Luck!

[Guillaume]

Note:

If you don't have the neural network toolbox, an easy way to generate the same as the above is with ndgrid:

[xx, yy, zz] = ndgrid(x, y, z);
[xx(:), yy(:), zz(:)].'

generates the exact same output (I wouldn't bother with the transpose and just have the combinations as rows)

[Chaya N]

You are absolutely correct! The memory implications of a large number of combinations is daunting though.

[Evan Meichtry]

Thanks Chaya and Guillaume, this is definitely the right function for the job (although the scope of the job may have to narrow ;) ...)

The issue now is how to dynamically use ndgrid. This is my current code:

    Cys = {'ag' 'az' 'ax'};
    Asp = {'ba' 'ba' 'bd'};
    Glu = {'cd' 'cs' 'cf'};
    [xx, yy, zz] = ndgrid(1:numel(Cys), 1:numel(Asp), 1:numel(Glu));
    output_x = [Cys(xx(:)).' Asp(yy(:)).' Glu(zz(:)).'];
output_x =
  27×3 cell array
    'ag'    'ba'    'cd'
    'az'    'ba'    'cd'
    'ax'    'ba'    'cd'
    etc.......

However, since I want to do this dynamically for varying amounts and orders of proteins, when I create a higher level cell array:

RNA_code = {Cys, Asp, Glu};
mesh_capture = cell(1,numel(RNA_code));
[mesh_capture{:}] = ndgrid(1:numel(RNA_code{:}));
output_x = RNA_code{:}(mesh_capture{:}).';

This throws " Error using numel Bad subscripting index." I'm out of my league with all this multilevel indexing so the mesh_capture code is something I tried to adapt from another example but evidently I'm misunderstanding multi-level indexing.

[Chaya N]

Hello Evan, Are you trying to generate the same 27x3 cell array output_x from your multi-level indexing (I am concentrating on the above example for now, then we can extend it to larger data) or are you trying to put each combination (row) in a cell by itself (to produce a 27x1 cell array)? Could you please clarify?

[Guillaume]

Evan, if you have whichever toolbox combvec comes with then use that as it abstracts all the difficulties of generating outputs and inputs for ndgrid. Otherwise, here is the generic way of using ndgrid:

%input: RNA_code, a cell array of arbitrary size containing vectors also of arbitrary size.
ndgridargs = cellfun(@(v) 1:numel(v), RNA_code, 'UniformOutput', false);  %generate inputs for ndgrid
[ndgridargs{:}] = ndgrid(ndgridargs{:});  %reuse cell array for output, since it's the right size
allcombs = cellfun(@(c, idx) reshape(c(idx), [], 1), RNA_code, ndgridargs, 'UniformOutput', false);  %use ndgridargs to index respective vector after reshaping into columns
allcombs = [allcombs{:}]  %concatenate all horizontally