首頁(yè) 猿問(wèn) 生成包含從n個(gè)向量中提取的所有元素...

生成包含從n個(gè)向量中提取的所有元素組合的矩陣。

源碼算法與數(shù)據(jù)結(jié)構(gòu)

慕村9548890 2019-06-05 14:32:04

生成包含從n個(gè)向量中提取的所有元素組合的矩陣。這個(gè)問(wèn)題經(jīng)常以一種或另一種形式出現(xiàn)(例如，參見(jiàn)這里或這里)。所以我想我應(yīng)該以一種一般的形式呈現(xiàn)出來(lái)，并給出一個(gè)答案，以供將來(lái)參考。給定任意數(shù)目n可能大小不同的向量，生成一個(gè)n-列矩陣，其行描述從這些向量中提取的所有元素的組合(笛卡爾積)。例如,vectors = { [1 2], [3 6 9], [10 20] }應(yīng)給予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 ]

查看完整描述

3 回答

RISEBY

TA貢獻(xiàn)1856條經(jīng)驗(yàn) 獲得超5個(gè)贊

這個(gè)ndgrid函數(shù)幾乎給出了答案，但有一個(gè)警告：n必須明確定義輸出變量才能調(diào)用它。自n是任意的，最好的方法是使用逗號(hào)分隔列表(從單元格數(shù)組生成的n作為輸出。結(jié)果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

反對(duì) 回復(fù) 2019-06-05

慕仙森

TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超8個(gè)贊

簡(jiǎn)單一點(diǎn).。如果您有神經(jīng)網(wǎng)絡(luò)工具箱，您可以簡(jiǎn)單地使用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

如果您想要有問(wèn)題的矩陣，可以使用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(類(lèi)型)edit combvec在命令窗口中，您將看到它使用的代碼與@LuisMendo的答案不同。我不能說(shuō)哪一個(gè)整體上更有效率。

如果碰巧有一個(gè)矩陣，其行與以前的單元格數(shù)組類(lèi)似，則可以使用：

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

反對(duì) 回復(fù) 2019-06-05

慕妹3146593

TA貢獻(xiàn)1820條經(jīng)驗(yàn) 獲得超9個(gè)贊

我已經(jīng)對(duì)兩種建議的解決方案做了一些基準(zhǔn)測(cè)試。基準(zhǔn)測(cè)試代碼基于timeit功能，并包括在這篇文章的末尾。

我考慮兩種情況：大小的三個(gè)向量n，以及三個(gè)大小向量n/10, n和n*10分別(這兩種情況給出相同數(shù)目的組合)。n最多可達(dá)240(選擇此值是為了避免在筆記本電腦中使用虛擬內(nèi)存)。

結(jié)果如下圖所示。這個(gè)ndgrid-基于解決方案的持續(xù)時(shí)間被認(rèn)為比combvec..值得注意的是，combvec在不同大小的情況下，變化要少一些。

基準(zhǔn)代碼

功能ndgrid-基于基礎(chǔ)的解決辦法：

function combs = f1(vectors)n = numel(vectors); %// number of vectorscombs = 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 ordercombs = cat(n+1, combs{:}); %// concat the n n-dim arrays along dimension n+1combs = reshape(combs,[],n);

功能combvec解決辦法：

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

通過(guò)調(diào)用來(lái)測(cè)量時(shí)間的腳本timeit關(guān)于這些職能：

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

反對(duì) 回復(fù) 2019-06-05