CODEWITHSUNDEEP
matlab
Star
Star

Reputation: 2299

Fast algorithm to get combinations in Matlab?

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,:)=[];

The function makeindex is 

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

Upvotes: 0

Views: 210

Answers (1)

Clemens
Clemens

Reputation: 245

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';

For n = 10: Elapsed time is 0.000976 seconds.

Old code: Elapsed time is 32.804602 seconds.

n=15: Elapsed time is 0.000866 seconds.

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

Upvotes: 3

Related Questions