清空筛选条件
清空筛选条件

Faster way for all possible arrangements

8 次查看（过去 30 天）
endeavour90
endeavour90 2012-4-1
currently my .m file looks like this
for a = 1 : 47
for b = a+1 : 48
for c = b+1 : 49
for d = c+1 : 50
fprintf('%d %d %d %d \n',a,b,c,d);
end
end
end
I am trying to generate sets of 4 elements from 1,2,3,...50 i.e. {1,2,3,4},{1,2,3,5},...{1,2,3,50},{1,2,4,5},..{47, 48, 49, 50}. Hence, in total there are C(50,4) sets. I would like to know whether there are any faster alternatives than these 4 nested loops? The order in one set does not necessarily in increasing order. i.e. it is ok if the code generate {4,1,2,3} rather than {1,2,3,4}.

请先登录，再回答此问题。

回答（4 个）

Jan
Jan 2012-4-5
FEX: vchoosek:
q = vchoosek(1:50, 4);
This needs 0.015 sec under Matlab 2009a/64. Matlab's nchoosek needs 0.9 sec.
If the order matters, this means if you want to get {1,2,3,4} and {1,3,2,4} etc, use FEX: vchooseko.
  2 个评论
endeavour90
endeavour90 2012-4-5
Is there a way to generate the sets row by row instead of storing all the combination first in a matrix? I am afraid that I also need to generate combination of 7 elements from 50 elements
Jan
Jan 2012-4-5
The posted function works for UINT8 values also, which need 1 byte per element compared to 8 for DOUBLEs:
q = vchoosek(uint8(1:50), 7)

请先登录，再进行评论。

Daniel Shub
Daniel Shub 2012-4-4
I think the fullfact function from the stats toolbox gets you close.
x = fullfact([50,50,50,50]);
Although you seem to be preventing sequences with repeats so you will need to find those after the fact.
Richard Brown
Richard Brown 2012-4-5
What you are currently doing is probably pretty close to optimal using native Matlab code. Depending on what you are doing you may be able to vectorise the inner loop to get a little more efficiency.
For example, it's faster than nchoosek:
N = nchoosek(50, 4);
V = zeros(N, 4);
idx = 0;
tic
for d = 1 : 47
for c = d+1 : 48
for b = c+1 : 49
for a = b+1 : 50
idx = idx + 1;
V(idx, :) = [d c b a];
end
end
end
end
toc
tic
V = nchoosek(1:50, 4);
toc
On my machine I get 0.1 and 0.6 seconds, respectively. The approach is still feasible with 50 and 7 too - on my machine it only takes about 1.1 seconds to iterate through all ~100,000,000 combinations (obviously you shouldn't fill up a matrix (like V) that big though, you'll slay your memory).
Sometimes simple is best.
  1 个评论
endeavour90
endeavour90 2012-4-5
I notice that the nested loop method is not that flexible. If I want to generate subset of 4 to 15, then I need to change the code by adding 1 'for' loop for each case. However if I used nchoosek or vchoosek function, then I just need to use 1 loop, say
for i = 4 : 15
nchoosek(1:50,i)
end
However, the only downside is that I want to generate the set row by row instead of the whole matrix at once.

请先登录，再进行评论。

Richard Brown
Richard Brown 2012-4-11
If you want to use native Matlab looping, but keep the benefit of flexibility (different n or k), then you can unroll the loops:
N = nchoosek(n, k);
v = 1:k; % first v
L = (n-k+1):n;
for i = 2:N
v(k) = v(k) + 1;
j = k;
while v(j) == (L(j) + 1)
v(j:k) = (v(j-1) + 2):(v(j-1)+2+k-j);
v(j-1) = v(j-1) + 1;
j = j - 1;
end
% useful v for your iteration is here
end
This code can probably be optimised a bit, but it will do what you want - the v vector at the end of each iteration is what you'd use. It will be a bit slow on 50C7 - 23 seconds on my computer, but that's not hugely surprising.

类别

在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by