javascript - Greplin 编程挑战第 3 级(Matlab)

Question

在 Greplin 挑战级别 3 中，需要计算总和为列表中另一个元素的子集的数量。请参阅Greplin 和 Challenge Description and Python code 。 我还找到了this code in 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查找一次获取 k 项的 n 项的所有可能组合。使用竞赛的示例:

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。