从给定向量生成矩阵

Question

我试图在Matlab中生成一个特定类型的o矩阵。

我需要根据以下规则对特定类型的数据进行修改：

• 首先我必须选择一个等级g(比如说，最大6(，然后我必须选择每行元素的数量n(最大18(；

• 这些数字是等级为g的特定多项式的幂；

• 矩阵中每行的总和不允许大于所选择的g等级；

• 每行最大的元素是所选择的g。

对于g = 2、n = 2，矩阵将如下所示：

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

对于g = 2和n = 3，矩阵将如下所示：

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]

如何生成数组元素的所有可能组合？

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...

我已经用perms、nchoosek、repelem、repmat、for-loops、unique、matrix concatenations尝试过了，但我找不到，也找不到算法。

Answer 1

您可以首先通过重复和重排生成[0..g]的所有n排列，然后选择允许的组合：

% 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, :);

正如我在评论中已经说过的，上面的代码在时间和内存方面都非常低效。例如，当我为g=6和n=9运行它时，MATLAB会给出以下错误：

使用零时出错请求的23667689815x9(1587.0GB(数组超过最大数组大小首选项
。。。

要减少内存消耗，可以执行以下操作：

% 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');

在上面的代码中，使用@knedlsepp的实现生成了具有g的重复的第一个n排列。滤波后只保留其和小于或等于g的组合。在下一步中，将计算这些组合的所有重排。对于g=6和n=9情况，这里仍然需要超过13秒才能找到5005组合。