matlab 生成一个包含n个向量中所有元素组合的矩阵(笛卡尔积)

tvmytwxo  于 8个月前  发布在  Matlab
关注(0)|答案(4)|浏览(108)

这个问题经常以这样或那样的形式出现(例如参见herehere)。因此,我想我将以一种一般的形式提出它,并提供一个答案,以供将来参考。
给定一个任意数量n的可能不同大小的向量,生成一个n列矩阵,其行描述从这些向量中提取的元素的所有组合(笛卡尔积)。
比如说,

vectors = { [1 2], [3 6 9], [10 20] }

应该给予

combs = [ 1     3    10
          1     3    20
          1     6    10
          1     6    20
          1     9    10
          1     9    20
          2     3    10
          2     3    20
          2     6    10
          2     6    20
          2     9    10
          2     9    20 ]
pu3pd22g

pu3pd22g1#

ndgrid函数几乎给出了答案,但有一个警告:n输出变量必须显式定义才能调用它。由于n是任意的,因此最好的方法是使用comma-separated list(由n单元的单元阵列生成)作为输出。然后将得到的n矩阵连接成所需的n列矩阵:

vectors = { [1 2], [3 6 9], [10 20] }; %// input data: cell array of vectors

n = numel(vectors); %// number of vectors
combs = cell(1,n); %// pre-define to generate comma-separated list
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1}); %// the reverse order in these two
%// comma-separated lists is needed to produce the rows of the result matrix in
%// lexicographical order 
combs = cat(n+1, combs{:}); %// concat the n n-dim arrays along dimension n+1
combs = reshape(combs,[],n); %// reshape to obtain desired matrix
xdyibdwo

xdyibdwo2#

简单一点...如果你有神经网络工具箱,你可以简单地使用combvec

vectors = {[1 2], [3 6 9], [10 20]};
combs = combvec(vectors{:}).' % Use cells as arguments

它以稍微不同的顺序返回一个矩阵:

combs =

     1     3    10
     2     3    10
     1     6    10
     2     6    10
     1     9    10
     2     9    10
     1     3    20
     2     3    20
     1     6    20
     2     6    20
     1     9    20
     2     9    20

如果你想要问题中的矩阵,你可以使用sortrows

combs = sortrows(combvec(vectors{:}).')
% Or equivalently as per @LuisMendo in the comments: 
% combs = fliplr(combvec(vectors{end:-1:1}).')

这给

combs =

     1     3    10
     1     3    20
     1     6    10
     1     6    20
     1     9    10
     1     9    20
     2     3    10
     2     3    20
     2     6    10
     2     6    20
     2     9    10
     2     9    20

如果您查看combvec的内部(在命令窗口中键入edit combvec),您将看到它使用的代码与@LuisMendo的答案不同。我不能说哪一个更有效率。
如果你碰巧有一个矩阵,它的行类似于前面的单元数组,你可以用途:

vectors = [1 2;3 6;10 20];
vectors = num2cell(vectors,2);
combs = sortrows(combvec(vectors{:}).')
zvms9eto

zvms9eto3#

我已经对这两个提议的解决方案做了一些基准测试。基准测试代码基于timeit function,并包含在本文的末尾。
我考虑两种情况:三个大小为n的向量,以及三个大小分别为n/10nn*10的向量(两种情况给予相同的组合数目)。n240(我选择这个值是为了避免在笔记本电脑中使用虚拟内存)。
结果如下图所示。基于ndgrid的解决方案始终比combvec耗时更少。同样有趣的是,combvec所花费的时间在不同大小的情况下变化得不那么规律。

基准代码

基于ndgrid的解决方案的功能:

function combs = f1(vectors)
n = numel(vectors); %// number of vectors
combs = cell(1,n); %// pre-define to generate comma-separated list
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1}); %// the reverse order in these two
%// comma-separated lists is needed to produce the rows of the result matrix in
%// lexicographical order
combs = cat(n+1, combs{:}); %// concat the n n-dim arrays along dimension n+1
combs = reshape(combs,[],n);

combvec解决方案的功能:

function combs = f2(vectors)
combs = combvec(vectors{:}).';

通过在这些函数上调用timeit来测量时间的脚本:

nn = 20:20:240;
t1 = [];
t2 = [];
for n = nn;
    %//vectors = {1:n, 1:n, 1:n};
    vectors = {1:n/10, 1:n, 1:n*10};
    t = timeit(@() f1(vectors));
    t1 = [t1; t];
    t = timeit(@() f2(vectors));
    t2 = [t2; t];
end
qlckcl4x

qlckcl4x4#

这里有一个自己动手的方法,让我高兴地咯咯笑,使用nchoosek,虽然它 * 不 * 比@Luis Mendo的公认解决方案更好。
对于给定的示例,在运行1,000次后,该解决方案平均花费了我的机器0.00065935 s,而接受的解决方案为0.00012877 s。对于较大的向量,根据@Luis Mendo的基准测试帖子,这个解决方案始终比公认的答案慢。尽管如此,我还是决定把它贴出来,希望你能从中找到一些有用的东西:

验证码:

tic;
v = {[1 2], [3 6 9], [10 20]};

L = [0 cumsum(cellfun(@length,v))];
V = cell2mat(v);

J = nchoosek(1:L(end),length(v));
J(any(J>repmat(L(2:end),[size(J,1) 1]),2) | ...
  any(J<=repmat(L(1:end-1),[size(J,1) 1]),2),:)  = [];

V(J)
toc

ans =

 1     3    10
 1     3    20
 1     6    10
 1     6    20
 1     9    10
 1     9    20
 2     3    10
 2     3    20
 2     6    10
 2     6    20
 2     9    10
 2     9    20

Elapsed time is 0.018434 seconds.

说明:

L使用cellfun获取每个向量的长度。虽然cellfun基本上是一个循环,但考虑到向量的数量必须相对较低,因此它在这里是有效的。
V连接所有向量,以便稍后访问(这假设您将所有向量输入为行。v'将适用于列向量。)
nchoosek获取从元素总数L(end)中挑选n=length(v)元素的所有方法。这里的组合会比我们需要的多

J =

 1     2     3
 1     2     4
 1     2     5
 1     2     6
 1     2     7
 1     3     4
 1     3     5
 1     3     6
 1     3     7
 1     4     5
 1     4     6
 1     4     7
 1     5     6
 1     5     7
 1     6     7
 2     3     4
 2     3     5
 2     3     6
 2     3     7
 2     4     5
 2     4     6
 2     4     7
 2     5     6
 2     5     7
 2     6     7
 3     4     5
 3     4     6
 3     4     7
 3     5     6
 3     5     7
 3     6     7
 4     5     6
 4     5     7
 4     6     7
 5     6     7

由于v(1)中只有两个元素,因此我们需要丢弃任何J(:,1)>2的行。类似地,其中J(:,2)<3J(:,2)>5等.使用Lrepmat,我们可以确定J的每个元素是否在其适当的范围内,然后使用any丢弃包含任何坏元素的行。
最后,这些不是来自v的实际值,只是索引。V(J)将返回所需的矩阵。

相关问题