Create all possible Mx1 vectors from an Nx1 vector in MATLAB

Question

I am trying to create all possible 1xM vectors (word) from a 1xN vector (alphabet) in MATLAB. N is > M. For example, I want to create all possible 2x1 "words" from a 4x1 "alphabet" alphabet = [1 2 3 4];

I expect a result like:

[1 1]
[1 2]
[1 3]
[1 4]
[2 1]
[2 2]
...

I want to make M an input to my routine and I do not know it beforehand. Otherwise, I could easily do this using nested for-loops. Anyway to do this?

Here's the question that gave me the clue to the compact answer: http://stackoverflow.com/questions/9834254/cartesian-product-in-matlab (I will take credit for knowing to search for "matlab cartesian product") — Ben Voigt, Nov 20 '13 at 23:11
@BenVoigt I [should have known it too](http://stackoverflow.com/questions/19991279/permutations-of-parameters-i-e-cartesian-product-into-a-multi-dimensional-arr)! — chappjc, Nov 20 '13 at 23:13
This has been asked _so many_ times. Here are possible duplicates: [How to generate all pairs from two vectors in MATLAB using vectorised code?](http://stackoverflow.com/questions/7446946/how-to-generate-all-pairs-from-two-vectors-in-matlab-using-vectorised-code) and [Generate all possible combinations of the elements of some vectors](http://stackoverflow.com/questions/4165859/matlab-generate-all-possible-combinations-of-the-elements-of-some-vectors) — Eitan T, Nov 21 '13 at 06:25

Ben Voigt · Answer 1 · 2013-11-20T23:25:08.803

5

Try

[d1 d2] = ndgrid(alphabet);
[d2(:) d1(:)]

To parameterize on M:

d = cell(M, 1);
[d{:}] = ndgrid(alphabet);
for i = 1:M
    d{i} = d{i}(:);
end
[d{end:-1:1}]

In general, and in languages that don't have ndgrid in their library, the way to parameterize for-loop nesting is using recursion.

[result] = function cartesian(alphabet, M)
    if M <= 1
        result = alphabet;
    else
        recursed = cartesian(alphabet, M-1)
        N = size(recursed,1);
        result = zeros(M, N * numel(alphabet));
        for i=1:numel(alphabet)
            result(1,1+(i-1)*N:i*N) = alphabet(i);
            result(2:M,1+(i-1)*N:i*N) = recursed;  % in MATLAB, this line can be vectorized with repmat... but in MATLAB you'd use ndgrid anyway
        end
    end
end

edited Nov 20 '13 at 23:25

answered Nov 20 '13 at 23:00

Ben Voigt

277,958
43
419
720

Haha, very concise! +1 – chappjc Nov 20 '13 at 23:01
Well, I haven't tested it. But it *should* work, with maybe some tweaking. – Ben Voigt Nov 20 '13 at 23:02
There, both ordered and parameterized! And tested, though on Matlab Mobile so I can't easily cut+paste here. – Ben Voigt Nov 20 '13 at 23:07

Luis Mendo · Accepted Answer · 2013-11-20T23:13:58.140

1

To get all k-letter combinations from an arbitrary alphabet, use

n = length(alphabet);
aux = dec2base(0:n^k-1,n)
aux2 = aux-'A';
ind = aux2<0;
aux2(ind) = aux(ind)-'0'
aux2(~ind) = aux2(~ind)+10;
words = alphabet(aux2+1)

The alphabet may consist of up to 36 elements (as per dec2base). Those elements may be numbers or characters.

How this works:

The numbers 0, 1, ... , n^k-1 when expressed in base n give all groups of k numbers taken from 0,...,n-1. dec2base does the conversion to base n, but gives the result in form of strings, so need to convert to the corresponding number (that's part with aux and aux2). We then add 1 to make the numbers 1,..., n. Finally, we index alphabet with that to use the real letters of numbers of the alphabet.

Example with letters:

>> alphabet = 'abc';
>> k = 2;

>> words

words =

aa
ab
ac
ba
bb
bc
ca
cb
cc

Example with numbers:

>> alphabet = [1 3 5 7];
>> k = 2;

>> words

words =

     1     1
     1     3
     1     5
     1     7
     3     1
     3     3
     3     5
     3     7
     5     1
     5     3
     5     5
     5     7
     7     1
     7     3
     7     5
     7     7

edited Nov 20 '13 at 23:13

answered Nov 20 '13 at 22:16

Luis Mendo

110,752
13
76
147

2

when `base` is greater than 10, I don't think the subtracting-`'0'` trick is going to work right. – Ben Voigt Nov 20 '13 at 22:57
Why does subtracting '0' turn a string to a number? @BenVoigt Unfortunately, I'm actually using a base > 10, and it doesn't work like you said. – SleepingSpider Nov 20 '13 at 23:04
@iab Corrected. Less elegant but hey – Luis Mendo Nov 20 '13 at 23:15
@LuisMendo I chose this as best answer because it had no for-loops involved and the working was well explained. Not to detract from the other solutions, but I find this routine the easiest to understand, and it's easy to quickly tell what the code is doing. – SleepingSpider Nov 21 '13 at 12:02

score 0 · Answer 3 · answered Nov 20 '13 at 23:23

0

use ndgrid function in Matlab

[a,b] = ndgrid(alphabet)

answered Nov 20 '13 at 23:23

ChuNan

1,131
2
11
27

Did you see Ben Voigt's answer by any chance? – chappjc Nov 20 '13 at 23:24

Create all possible Mx1 vectors from an Nx1 vector in MATLAB

3 Answers3