CODEWITHSUNDEEP
matlabmatrixvector
netse g
netse g

Reputation: 25

Generating a Matrix from a given vector

Im trying to generate a specific type o matrix in Matlab.

I need to modify it for specific types of data with the following rules:

For g = 2, n = 2 the matrix will look like this:

A = [0 0; 
     0 1; 
     1 0; 
     0 2; 
     2 0; 
     1 1]

For g = 2, n = 3 the matrix will look like this:

A = [0 0 0; 
     0 0 1; 
     0 0 2; 
     0 1 0; 
     0 2 0; 
     1 0 0; 
     2 0 0; 
     0 1 1; 
     1 0 1;
     1 1 0]

How can I generate all possible combinations of an array elements?

Ex : given v = [0 1 2];

Result = [0 0 0;
          0 0 1;
          0 1 0;
          0 1 1;
          1 0 0;
          1 0 1;
          1 1 0;
          1 1 1;
          0 0 2;
          0 2 0;
          2 0 0;
          2 0 1;
          2 1 1;
          2 1 2;
            ...]
and so on...

I've tried this with perms, nchoosek, repelem, repmat, for-loops, unique, matrix concatenations, everything but I couldn't be able to find and algorithm.

Upvotes: 2

Views: 113

Answers (1)

saastn
saastn

Reputation: 6015

You can first generate all n permutations of [0..g] with repetition and rearrangement, then select allowed combinations:

% all n permutations of [0..g] (with repetition and rearrangement)
powers = unique(nchoosek(repmat(0:g, 1, n), n), 'row');
% allowed set of powers
powers = powers(sum(powers, 2) <= g, :);

As I already said in comments, the above code is extremely time and memory inefficient. For example when I run it for g=6 and n=9, MATLAB gives the following error:

Error using zeros Requested 23667689815x9 (1587.0GB) array exceeds maximum array size preference.
...

To reduce memory consumption, you can do the following:

% all n permutations of [0..g] (with repetition)
gPerms = nmultichoosek(0:g, n);
% allowed set of powers
allowed = gPerms(sum(gPerms, 2) <= g, :);
% all permutations of [1..n] (no repetition)
nPerms = perms(1:n);
% all n permutations of [0..g] (with repetition and rearrangement)
arranges = arrayfun(@(i) allowed(:, nPerms(i, :)), ...
    1:size(nPerms, 1), 'UniformOutput', false)';
powers = cell2mat(arranges);
% unique set of permutations
powers = unique(powers, 'rows');

In the above code, first n permutations with repetition of g is generated using @knedlsepp's implementation. The filtered to keep only combinations that their sums is less than or equal to g. In next step all rearrangements of these combinations are calculated. It still takes more than 13 seconds here to find 5005 combinations for the g=6 and n=9 case.

Upvotes: 1

Related Questions