Как перечислить все возможные подмножества с фиксированным числом элементов и сумму элементов в Matlab

Question

Учитывая множество возможных значений I, как я могу перечислить все возможные подмножества векторов длины L таким образом, что сумма элементов составляет k с использованием Matlab?

Say I = [0 0 0 1 1 1 2 2 2 3 3 3] L = 3, и к = 4. Среди возможных подмножеств: [0 1 3] [0 3 1] [1 0 3] [1 3 0] [3 0 1] [3 1 0] [0 2 2] [2 0 2] [2 2 0] и т.д.

решение я реализую сейчас заключается в следующем: Создание п вложенными для петель, где п является количество уникальных элементов в я, пределы быть от 0 до максимального количества раз, когда элемент i может использоваться.

Чтобы сделать его работать быстрее, я также изменил пределы, так что сумма будет автоматически K без меня проверять в конце концов. В этом процессе мне удалось удалить один для цикла.

Такой алгоритм действительно работает, но мой код действительно выглядит грязным (представьте, если у меня есть 10 вложенных циклов: O). Что еще более важно, я считаю, что трудно автоматизировать процедуру для любого набора входов (I, L, к) с помощью этого.

Можете ли вы придумать какой-либо другой способ сделать это? Я думаю, что рекурсия будет работать отлично, но я не очень хорош в этом отношении, и мне трудно реализовать ее в Matlab.

PS. Я также попробовал combnk (I, L), а затем проверить позже, если сумма k, но оказывается, что код работает очень медленно для больших I и L.

Answer 1

Это один из способов использования рекурсии (без каких-либо петель) :

function [ comb ] = enumAll(I,L,K) 

%//obtain a unique vector of I 
I = unique(I); 

%//base case: for the last place, enumerate all possibilites from 1:K 
if L==1 
    comb = (1:K).'; %//' 
    return; 
end 

%//at each recursion step, find the (possibilities of the remaining positions), .. 
suffixes = enumAll(I,L-1,K); 
%//..and add the possibilities of this position with all of them 
comb = reshape(repmat((((1:K).')*(10^(L-1))).' , [length(suffixes) 1]), [length(suffixes)*K 1]) + repmat(suffixes,[K 1]); 

end