algorithm - 计算给出数组中最小标准偏差的子集

Question

让我们有一个大小为 N 的向量。例如:

x = rand(N,1)

我想计算向量中长度为 K 的子集的最小标准差。

当 N 和 K 较小时，很容易找到最佳子集，因为我可以使用 nchoosek(N,K) 来枚举所有可能的子集。但是当 N 和 K 的值大于我们说的 N=50 和 K=25 时，nchoosek 无法计算组合，因为可能的子集的大小非常大。

我想知道是否有更好的算法来有效地计算数组中给出最小标准差的子集。例如通过动态规划。有什么想法吗？

更新:

我在答案后循环实现了它，并与组合解决方案进行了比较。结果始终相同，但速度提升是前所未有的。

n = 20;
k = 10;
x = rand(n,1);
C = nchoosek(x, k);

tic
mins = realmax;
for i = 1:size(C,1)
    s = std(C(i,:));
    if s < mins
        mins = s;
        bestC = C(i,:);
    end
end
toc

tic
[x2, j] = sort(x);
mins2 = realmax;
for i = 1:(n-k+1)
    s = std(x2(i:(i+k-1)));
    if s < mins2
        mins2 = s;
        idx = j((i:(i+k-1)));
    end
end
toc

if mins == mins2
    'Equal'
end

给予

Elapsed time is 7.786579 seconds.
Elapsed time is 0.002068 seconds.

ans =

Equal

Answer 1

对数组进行排序，然后使用长度为 K 的滚动窗口一次计算。

我相信这会给你正确的答案，如果我能证明的话，我会考虑的。

Hand-wavey argument，在“extend this”部分可能存在逻辑漏洞:

考虑列表中的元素 x。让我们尝试找出包含此元素的一组大小为 2 的最小标准差。我们将通过选择 x 和最接近 x 的元素来获得它。将其扩展到 k 元素，我们将得到一个集合，它是包含 x 的排序列表的连续部分。因此，要选择 k 元素的最小子集(即对于任何 x)，我们只需如前所述迭代排序列表。