生成包含取自n个向量的所有元素组合的矩阵

Question

这个问题经常以某种形式出现(例如,见此处或此处).所以我认为我会以一般形式呈现它,并提供一个可能供将来参考的答案.

给定任意数量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 ]

Answer 1

该ndgrid函数几乎给出了答案,但有一点需要注意:n输出变量必须明确定义才能调用它.由于n是任意的,最好的方法是使用以逗号分隔的列表(从带有单元格的单元格数组生成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

Answer 2

稍微简单一点......如果你有神经网络工具箱,你可以简单地使用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{:}).')

Answer 3

我已经对两个提出的解决方案做了一些基准测试.基准测试代码基于该timeit功能,并包含在本文末尾.

我考虑两种情况:尺寸的三个矢量n,和尺寸的三个矢量n/10,n并n*10分别(这两种情况下,得到相同的数量的组合).n最多变化240(我选择此值以避免在我的笔记本电脑中使用虚拟内存).

结果如下图所示.该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