サイズのベクトルを作成しましょう 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
回答：
回答№1の場合は3配列を並べ替えてから、長さのローリングウィンドウを使用して1回のパスでこれを計算します K.
私はこれがあなたに正しい答えを与えると確信しています、私がそれを証明できるかどうか考えます。
「これを拡張する」部分のロジックにギャップがある可能性のある、手振りの議論：
要素を考える x あなたのリストから。この要素を含むサイズ2のセットの最小標準偏差を見つけてみましょう。これを選択して取得します。 x およびに最も近い要素 x。これをに拡張する k 要素と私たちは "を含むソートされたリストの連続した部分であるセットを取得します x。の最小サブセットを選択するには k 要素（つまり、 x）したがって、前述のように、ソートされたリストを反復処理する必要があります。