CODEWITHSUNDEEP
arraysalgorithmmatlabvector
SleepingSpider
SleepingSpider

Reputation: 1228

Create all possible Mx1 vectors from an Nx1 vector in MATLAB

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?

Upvotes: 3

Views: 627

Answers (3)

Ben Voigt
Ben Voigt

Reputation: 283823

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

Upvotes: 5

ChuNan
ChuNan

Reputation: 1151

use ndgrid function in Matlab

[a,b] = ndgrid(alphabet)

Upvotes: 0

Luis Mendo
Luis Mendo

Reputation: 112759

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

Upvotes: 1

Related Questions