在Matlab中获得组合的快速算法? [英] Fast algorithm to get combinations in Matlab?

问题描述

我需要在Matlab中调整以下算法，因为当n很大时，步骤(2)中的双循环会花费很多时间(我应该能够为n=15运行该算法).有什么想法吗?

I need to adjust the following algorithm in Matlab because the double loop in step (2) takes to much time when n is large (I should be able to run the algorithm for n=15). Any ideas?

n=3; 

% (1) construct A: list of DISPOSITIONS of the elements of the set {0,1} in n 
%places (organise 2 elements in n places with possibility of repetitions and        the order matters) 

A=makeindex(n); %matrix 2^n x n (FAST)

% (2) modify A: it should give the list of COMBINATIONS of the elements of the set 
%{0,1} in n-1 places (organise 2 elements in n-1 places with repetitions and the 
%order does NOT matter), repeated twice:
% once when the n-th element is 0, the other when the n-th element is 1
Xr=A(:,n);  
m=sum(A,2);        %vector totalx1
                   %each element is the total number of ones in the
                   %corresponding row


drop=false(2^n,1);   %logical vector totalx1

for i=1:2^n
    parfor j=1:2^n
        if j>i
            if m(i)==m(j) && Xr(i)==Xr(j)  %(VERY SLOW)
               drop(j)=true;
            end
        end
    end

end

A(drop,:)=[];  

函数makeindex是

function [index]=makeindex(k)                                              %
total=2^k;                                                                 %
index=zeros(total,k);                                                      %                                                                       
for i=1:k                                                                  %
    ii=1;                                                                  %
    cc=1;                                                                  %
    c=total/(2^i);                                                         %
    while ii<=total                                                        %
        if cc <=c                                                          %
            index(ii,i)=1;                                                 %
            cc=cc+1;                                                       %
            ii=ii+1;                                                       %
        else                                                               %
            ii=ii+c;                                                       %
            cc=1;                                                          %
        end                                                                %
    end                                                                    %
end                                                                        %
                                                                           %
end     

推荐答案

如果那是您想要的解决方案，请按以下方法解决:

Here my solution if that's what you want:

A=zeros(n,2*n);
A(:,1)=1;
for i=2:2:n*2-1
    A(:,i-1)=circshift(A(:,i-1),[-1 0]);
    A(:,i)=A(:,i-1);
    A(end,i)=0;
    A(:,i+1)=A(:,i);
end
A(:,end-1)=circshift(A(:,end-1),[-1 0]);
A=A';

对于n = 10: 经过的时间是0.000976秒.

For n = 10: Elapsed time is 0.000976 seconds.

旧代码: 经过的时间是32.804602秒.

Old code: Elapsed time is 32.804602 seconds.

n = 15: 经过的时间是0.000866秒.

n=15: Elapsed time is 0.000866 seconds.

旧代码: ...仍在计算...;)

Old code: ... still calculating... ;)

这篇关于在Matlab中获得组合的快速算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！