matlab - 如何在Matlab中枚举具有固定元素数量和元素之和的所有可能子集

Question

给定一组可能的值I，如何枚举长度为L的所有可能的子集向量使用 Matlab 使得元素之和为 k？

说I=[0 0 0 1 1 1 2 2 2 3 3 3],L =3，并且k=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] 等

我现在正在实现的解决方案是这样的:创建n个嵌套for循环，其中n是I中唯一元素的数量，限制范围是从0到元素i可以使用的最大次数。

为了让它运行得更快，我还修改了限制，使得总和将自动为k，而无需我最后检查。在此过程中，我实际上成功地删除了一个 for 循环。

这样的算法确实有效，但我的代码看起来确实很困惑(想象一下，如果我有 10 个嵌套的 for 循环:O)。更重要的是，我发现很难对任何一组输入(I、L、< strong>k)使用这个。

你能想到其他方法来做到这一点吗？我认为递归在这里可以很好地工作，但我在这方面不是很好，而且我发现很难在 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