Generating a Matrix from a given vector

Question

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:

• First I have to choose a grade g (max 6 let's say) then I have to choose the number of elements per row n (max 18) ;

• These numbers are the powers of a specific polynomial of grade g ;

• The sum per row in the matrix is not allowed to be bigger than the chosen g grade ;

• The biggest element per row is the chosen g.

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.

Answer 1

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.