Greplin Programming Challenge Level 3 (Matlab)

Question

На уровне сложности Greplin 3 требуется подсчитать количество подмножеств, которые суммируют до другого элемента в списке. См. Greplin и Описание вызова и код Python . Я также нашел этот код в javascript , но нашел его гораздо менее понятным, чем Python.

У меня вопрос: есть ли какая-нибудь команда Matlab для поиска всех подмножеств массива, аналогично библиотеке комбинаций в python? Ответ на вызов в вашем ответе будет оценен.

Я пытался написать какой-то код для него, но он явно не работал так хорошо.

Nums = [3   4   9   14  15  19  28  37  47  50  54  56  59  61  70  73  78  81  92  95  97  99];
% Nums = [1, 2, 3, 4, 6];

SubsetCount = 0;
for Ind = 1:length(Nums)

    maxNum = Nums(Ind);
    s = setdiff( Nums, maxNum );
    NumSubsetsCountToIt = NumSubsetsCount( s,  maxNum);
    SubsetCount = SubsetCount + NumSubsetsCountToIt;

end
disp(SubsetCount);

function    NumSubsetsCountToIt = NumSubsetsCount( Nums, SumUpNum )
global OptionsToGetTo

NumSubsetsCountToIt = 0;
validNums = Nums;

if sum(validNums)==SumUpNum

    NumSubsetsCountToIt = 1;

else

    for Ind=length( validNums ):-1:1
        outNum = validNums(Ind);
        s = setdiff(validNums, outNum );
        NumSubsets = NumSubsetsCount( s, SumUpNum-outNum );
        NumSubsetsCountToIt = NumSubsetsCountToIt+NumSubsets;
    end
    NumSubsetsCountToIt = floor((NumSubsetsCountToIt+1)/2);

end

OptionsToGetTo(2, b) = NumSubsetsCountToIt;

Answer 1

Вы можете использовать функцию combnk, чтобы найти все возможные комбинации n предметов, взятых k за один раз. Используя пример конкурса:

values=[1,2,3,4,6];%# test vector
values=sort(values(:),'ascend');%#not needed here, but good to sort as indexing becomes easier in the end.
matchingSubsets=cell(numel(values)-1,1);%we don't need the trivial case of j=j. So, 1 less cell.

for i=2:numel(values)
    combinations=combnk(values,i);
    matchingSubsets{i-1}=combinations(sum(combinations(:,1:i-1),2)==combinations(:,i),:);%# this is where the sorting helps, as you now know that the last column is the max value.
end

Результат:

matchingSubsets{:}
ans =
   Empty matrix: 0-by-2

ans =
     2     4     6
     1     3     4
     1     2     3

ans =
     1     2     3     6

ans =
   Empty matrix: 0-by-5

Чтобы получить окончательный ответ, то есть количество подмножеств,

subsetSizes=cell2mat(cellfun(@size,matchingSubsets,'UniformOutput',false));
totalSubsets=sum(subsetSizes(:,1));

, что дает totalSubsets=4.