Генерация всех комбинаций с повторением с использованием MATLAB

Question

Как мне создать все k-комбинации с повторениями данного набора (также называемые k-мультикомбинациями или мультисубсетами), используя MATLAB?

Это похоже на декартово произведение, но две строки, которые отличаются только по сортировке, должны считаться одинаковыми (например, векторы [1,1,2]=~=[1,2,1] считаются одинаковыми), поэтому генерирует декартово произведение и затем применяет unique(sort(cartesianProduct,2),'rows') должен дать те же результаты.

Пример: звонок nmultichoosek(1:n,k) должен сгенерировать следующую матрицу:

nmultichoosek(1:3,3)
ans =
     1     1     1
     1     1     2
     1     1     3
     1     2     2
     1     2     3
     1     3     3
     2     2     2
     2     2     3
     2     3     3
     3     3     3

Answer 1

Мы можем использовать биекцию, упомянутую в статье в википедии, которая отображает комбинации без повторения типа n+k-1 choose k в k -комбинации размеров n, Мы генерируем комбинации без повторов и отображаем их, используя bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1);, Это приводит к следующей функции:

function combs = nmultichoosek(values, k)
%// Return number of multisubsets or actual multisubsets.
if numel(values)==1 
    n = values;
    combs = nchoosek(n+k-1,k);
else
    n = numel(values);
    combs = bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1);
    combs = reshape(values(combs),[],k);
end

Answer 2

Метод грубой силы: генерировать все кортежи, а затем сохранять только те, которые отсортированы. Не подходит для больших значений n или же k,

values = 1:3;                               %//  data
k = 3;                                      %//  data
n = numel(values);                          %//  number of values
combs = values(dec2base(0:n^k-1,n)-'0'+1);  %//  generate all tuples
combs = combs(all(diff(combs.')>=0),:);     %'// keep only those that are sorted

Answer 3

Это, вероятно, еще более жестокий (требующий большого объема памяти) метод, чем предыдущие посты, но читаемый в одной строке:

 combs = unique(sort(nchoosek(repmat(values,1,k),k),2),'rows');