performance - k-size 可能的数字组合按每个总和排序

Question

给定一组 n 个数字；按降序生成所有可能的 k 大小子集的代码是什么(减少每个值的总和)？

示例:

Set={9,8,6,2,1} => n=5 和 k=3。所以输出是:

[9,8,6] 
[9,8,2]
[9,8,1]
[9,6,2]
[9,6,1]
[8,6,2]
[8,6,1]
[9,2,1]
[8,2,1]
[6,2,1]

它是首选最高效的算法，但具有 NP 完全复杂度的算法(n 选择 k 排列)是答案。
Matlab Code中的逐一生成优先实现。或者可以确定其中有序列表的最大大小的解决方案(由此，对于更大的 n 和 k，可以使用近似值并返回该列表的特定大小而不计算所有可能性)。
注意:
1)请注意[9,2,1]在这个有序列表中的位置。所以索引排序不是正确答案。
2)这可能是一种类型Lexicographical order .

Answer 1

感谢 Divakar、Yvon 和 Luis，这个问题的可能答案之一:
SSC 中存在有序集合组合，所以

combs = nchoosek(Set,k);
[~,ind] = sort(sum(combs,2),'descend');
SSC = combs(ind,:);

如果你想要 Set 中每个数字数组的索引(具有唯一数字)，SSC 中的 num_arr 索引使用此代码

for i=1:k
    Index(i)=find(SSC(num_arr,j)==Set(1,:));
end

此代码返回 [1,3,5] for Index 中的 [9,6,1]。
< br/> 对于更大的 n
在这种情况下，计算非常耗时，甚至不切实际。一个近似可以解决这个问题，对于这种情况，您可以通过修改Matlab中的nchoosek.m找到第一个任意答案。