Výpočet podmnožiny s minimálnou štandardnou odchýlkou ​​v matici - algoritmus, matlab, kombinácie

Majme vektor veľkosti N, Napríklad:

x = rand(N,1)

Chcem vypočítať minimálnu štandardnú odchýlku podmnožiny dĺžky K vo vektore.

Kedy N a K sú malé, je ľahké nájsť najlepšiu podmnožinu, ktorú môžem použiť nchoosek(N,K) vymenovať všetky možné podmnožiny. Ale keď hodnoty N a K sú väčšie, ako povedzme N=50 a K=25, nchoosek nedokáže vypočítať kombinácie, pretože veľkosť možných podmnožín je obrovská.

Zaujímalo by ma, či existuje lepší algoritmus na efektívne vypočítanie podmnožiny, ktorá poskytuje najmenšiu štandardnú odchýlku v poli. Napríklad prostredníctvom dynamického programovania. Nejaké nápady?

aktualizovať:

Implementoval som ho do slučky po odpovediach a v porovnaní s kombinačným riešením. Výsledky sú vždy rovnaké, ale nárast rýchlosti je bezprecedentný.

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

poskytuje

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

ans =

Equal

odpovede:

Zoraďte pole a potom to vypočítajte v jednom priechode s rolovacím oknom dĺžky K.

Som si istý, že to vám dá správnu odpoveď, pomyslím si, či to dokážem.

Ručne zvlnený argument s možnou medzerou v logike v časti „rozšíriť túto“:

Zvážte prvok x zo svojho zoznamu. Pokúsme sa nájsť minimálnu smerodajnú odchýlku sady veľkosti 2 obsahujúcej tento prvok. Zistíme to výberom x a najbližší prvok k x. Rozšíriť na k prvkov a dostaneme množinu, ktorá je súvislou súčasťou triedeného zoznamu, ktorý obsahuje x. Ak chcete vybrať najmenšiu podmnožinu k prvky (t.j. pre akékoľvek x) preto musíme iba prechádzať zoradeným zoznamom, ako bolo popísané vyššie.