生成一个包含 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

Answer 4

这是一个让我高兴地咯咯笑的DIY方法，使用

nchoosek

，尽管它不比@Luis Mendo接受的解决方案更好。

对于给出的示例，运行 1,000 次后，该解决方案平均花费我的机器 0.00065935 秒，而接受的解决方案平均花费 0.00012877 秒。对于较大的向量，按照 @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

获取从元素总数

n=length(v)

中挑选

L(end)

元素的所有方法。 这里的组合会比我们需要的更多。

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)<3

，

J(:,2)>5

等...使用

L

和

repmat

，我们可以确定

J

的每个元素是否在其适当的范围内，然后使用

any

丢弃具有的行任何不良元素。

最后，这些不是

v

的实际值，只是索引。

V(J)

将返回所需的矩阵。