Создать матрицу, содержащую все комбинации элементов, взятых из n векторов

Ответ 1

Функция ndgrid почти дает ответ, но имеет одно предостережение: n выходные переменные должны быть явно определены для вызова. Так как n произвольно, лучше всего использовать список, разделенный запятыми (сгенерированный из массива ячеек с ячейками n) для вывода. Полученные матрицы n затем объединяются в искомую матрицу n -column:

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

Ответ 2

Немного проще... если у вас есть набор инструментов Neural Network, вы можете просто использовать 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{:}).')

Ответ 3

Я провела сравнительный анализ двух предлагаемых решений. Код бенчмаркинга основан на timeit function и включен в конце этого сообщения.

Я рассматриваю два случая: три вектора размера 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{:}).';

Script, чтобы измерить время, вызвав 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

Ответ 4

Вот мой метод, который заставлял меня хихикать с восторгом, используя nchoosek, хотя он не лучше, чем @Luis Mendo принял решение.

В приведенном примере после 1000 запусков это решение заняло мою машину в среднем 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) вернет желаемую матрицу.