Greplin编程挑战3级（Matlab）

[poster]

在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;

回答：

您可以使用功能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 。



更多&回答...