Gere uma matriz contendo todas as combinações de elementos retirados de n vetores

Esta questão aparece com bastante frequência de uma forma ou de outra (veja por exemplo aqui ou aqui ). Então eu pensei em apresentá-lo de uma forma geral e fornecer uma resposta que possa servir para referência futura.

Dado um número arbitrário n de vetores de tamanhos possivelmente diferentes, gere uma matriz de n colunas cujas linhas descrevem todas as combinações de elementos tiradas desses vetores (produto cartesiano).

Por exemplo,

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

deveria dar

 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 ] 

A function ndgrid quase dá a resposta, mas tem uma ressalva: n variables ​​de saída devem ser explicitamente definidas para chamá-la. Como n é arbitrário, a melhor maneira é usar uma lista separada por vírgula (gerada a partir de uma matriz de células com n células) para servir como saída. As n matrizes resultantes são então concatenadas na matriz da coluna n desejada:

 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 

Um pouco mais simples … se você tiver a checkbox de ferramentas Rede Neural, você pode simplesmente usar o combvec :

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

que retorna uma matriz em uma ordem ligeiramente diferente:

 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 

Se você quiser a matriz que está na pergunta, você pode usar sortrows :

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

que dá

 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 

Se você olhar os componentes internos do combvec (digite edit combvec na janela de comando), verá que ele usa um código diferente da resposta do @ LuisMendo. Eu não posso dizer o que é mais eficiente em geral.

Se acontecer de você ter uma matriz cujas linhas são semelhantes à matriz de células anterior, você pode usar:

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

Eu fiz alguns benchmarking nas duas soluções propostas. O código de benchmarking é baseado na function timeit e está incluído no final deste post.

Considero dois casos: três vetores de tamanho n e três vetores de tamanhos n/10 , n e n*10 respectivamente (ambos os casos fornecem o mesmo número de combinações). n é variado até um máximo de 240 (escolho este valor para evitar o uso de memory virtual no meu laptop).

Os resultados são dados na figura a seguir. A solução baseada em ndgrid é vista consistentemente em menos tempo que a combvec . Também é interessante notar que o tempo gasto pelo combvec varia um pouco menos regularmente no caso de tamanhos diferentes.

insira a descrição da imagem aqui


Código de benchmarking

Função para solução baseada em 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); 

Função para solução combvec :

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

Script para medir o tempo, chamando timeit sobre essas funções:

 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 

Aqui está um método do tipo “faça você mesmo” que me fez rir de alegria, usando nchoosek , embora não seja melhor do que a solução aceita de @Luis Mendo.

Para o exemplo dado, após 1.000 execuções, esta solução levou a minha máquina em média 0,00065935 s, versus a solução aceita 0,00012877 s. Para vetores maiores, seguindo o post de benchmarking de @Luis Mendo, esta solução é consistentemente mais lenta que a resposta aceita. No entanto, decidi publicá-lo na esperança de que talvez você encontre algo útil sobre isso:

Código:

 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. 

Explicação:

L obtém os comprimentos de cada vetor usando o cellfun . Embora o cellfun seja basicamente um loop, é eficiente aqui, considerando que seu número de vetores terá que ser relativamente baixo para que esse problema seja prático.

V concatena todos os vetores para facilitar o access mais tarde (isso pressupõe que você inseriu todos os seus vetores como linhas. V 'funcionaria para vetores de coluna.)

nchoosek obtém todas as maneiras de escolher n=length(v) elementos do número total de elementos L(end) . Haverá mais combinações aqui do que o que precisamos.

 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 

Como existem apenas dois elementos em v(1) , precisamos descartar todas as linhas onde J(:,1)>2 . Da mesma forma, onde J(:,2)<3 , J(:,2)>5 , etc ... Usando L e repmat , podemos determinar se cada elemento de J está em seu intervalo apropriado e, em seguida, usar any para descartar linhas que tem algum elemento ruim.

Finalmente, estes não são os valores reais de v , apenas índices. V(J) retornará a matriz desejada.