Huge matrix with Nchoosek

I have a program where I need all possible combinations between two variables(N and T). Facing "Out of Memory" problem whenever T increases 4. Is there any solution for this?

clear;
load('HD2255.mat');    
% spiky signal generation
N = 255;  %maximum users
T  = 10;    % number of spikes
a = zeros(N,1);  %creating N-by-1 all zero vector
C = nchoosek(1:N,T); %creating all the combination values between N and T
e= nchoosek(N,T);    %number of all possible combinations
x0 = zeros(N,1);     %creating N-by-1 all zero vector
count = 0;           %used in calculating success
%disp(C);
for K = 1:1:N        %K, m are two variables to identify the element in C
    a = zeros(N,1);     %creating N-by-1 all zero vector
    for m = 1:1:T;      %used to initiate loop for reading the elements in C
        i= C(K,m);  
        a(i) = 1;    %i defining the place of 1 in all zero vector a
        x0(1:N)=a;   %putting x0 as a
    end
        if a(i) ~= 0;  %implementing network conditions
       n = randn(1,1); % white gaussian noise, 0dB variance
       h = 1/sqrt(2)*[randn(1,1) + j*randn(1,1)]; % Rayleigh channel
       h_abs = abs(h);
       x0(i) = 1 * h_abs + 10^(-1/1)*n;
       y  = HD2255*x0;          % measurements with no noise
       lambda = 0.0001;      % regularization parameter
       rel_tol = 0.01;     % relative target duality gap actual 0.01
 
       [x,status]=l1_ls(HD2255,y,lambda,rel_tol);
   for s = 1:size(x0,1);   %starting a loop to calculate success
   for t = 1:size(x0,2);
       if x0(s,t) ~= 0;     %when x0 is avtive
        d(s,t) = abs(x0(s,t)) - abs(x(s,t)); %difference
        if d(s,t) < 0.1;      %success criteria
            count = count + 1;  %counting the number of times it is successful
           % cnt = count / e
            %perc = (cnt*100)/T
           % sta(s,t) = -1;
        %else sta(s,t) = 1;
        %fprintf('count\n', count)
        disp(count);
             end
   end
     end
end
 end
    end
%end
cnt = count / e
 perc = (cnt*100)/T

[Jos (10584)]

Do you really need them all? At the same time?

[Bruno Luong]

The number of combination is

nchoosek(255,10) ~ 2.6793e+17

And the size to store is

ans*10*8/(1024)^4 Tb = 1500 billion Tera bytes.

If your can process 100 of such combinations in 1 second, it takes you

nchoosek(255,10)/(100*3600*24*365) years = 84 millions years

to process.

[Muhammad Hamad]

Jos (10584)

I need them one by one. I need an array of all zeros but 1's only according to this combination. I need to use it through this way because of not having proper toolbox.

Bruno Luong

You are right, but I need those combinations one by one.

Is there anything I can do? Please suggest

[Bruno Luong]

"Is there anything I can do?"

First try to find a way to live more than 84 millions years.

You seem not understand what I'm saying: Working on combinations even one-by-one is a dead end.

[Stephen23]

"... I need those combinations one by one. Is there anything I can do?"

Be extremely patient.

[Muhammad Hamad]

Bruno Luong

I understand sir....

Stephen Cobeldick

Yes I became real "Patient" now

[John D'Errico]

Think of it like this - the art of mathematics is not throwing a computer at a problem, and waiting 60 million years or so, until it finishes. The art is finding a better way of solving your problem in a way that does not use brute force. So you need to look for a better approach, since you cannot solve it using brute force.

[Walter Roberson]

You are looking for over 2^57 combinations.

To finish in no more than 30 days, you would need to process 267934565633045025/(30*24*60*60) per second, which is about 10^11 per second. Your computer would need to be running at 100 Gigahertz times the number of hardware instructions required to process one combination.

With a clever algorithm, you just might be able to do the processing in a month on a good-quality GPU. However, GPUs would not be able to store the result, as it would take too much memory.

[Stephen23]

Original question asked by Hamad Gul (copied from Google Cache):

I have a program where I need all possible combinations between two variables(N and T). Facing "Out of Memory" problem whenever T increases 4. Is there any solution for this?

clear;
load('HD2255.mat');    
% spiky signal generation
N = 255;  %maximum users
T  = 10;    % number of spikes
a = zeros(N,1);  %creating N-by-1 all zero vector
C = nchoosek(1:N,T); %creating all the combination values between N and T
e= nchoosek(N,T);    %number of all possible combinations
x0 = zeros(N,1);     %creating N-by-1 all zero vector
count = 0;           %used in calculating success
%disp(C);
for K = 1:1:N        %K, m are two variables to identify the element in C
    a = zeros(N,1);     %creating N-by-1 all zero vector
    for m = 1:1:T;      %used to initiate loop for reading the elements in C
        i= C(K,m);  
        a(i) = 1;    %i defining the place of 1 in all zero vector a
        x0(1:N)=a;   %putting x0 as a
    end
        if a(i) ~= 0;  %implementing network conditions
       n = randn(1,1); % white gaussian noise, 0dB variance
       h = 1/sqrt(2)*[randn(1,1) + j*randn(1,1)]; % Rayleigh channel
       h_abs = abs(h);
       x0(i) = 1 * h_abs + 10^(-1/1)*n;
       y  = HD2255*x0;          % measurements with no noise
       lambda = 0.0001;      % regularization parameter
       rel_tol = 0.01;     % relative target duality gap actual 0.01
 
       [x,status]=l1_ls(HD2255,y,lambda,rel_tol);
   for s = 1:size(x0,1);   %starting a loop to calculate success
   for t = 1:size(x0,2);
       if x0(s,t) ~= 0;     %when x0 is avtive
        d(s,t) = abs(x0(s,t)) - abs(x(s,t)); %difference
        if d(s,t) < 0.1;      %success criteria
            count = count + 1;  %counting the number of times it is successful
           % cnt = count / e
            %perc = (cnt*100)/T
           % sta(s,t) = -1;
        %else sta(s,t) = 1;
        %fprintf('count\n', count)
        disp(count);
             end
   end
     end
end
 end
    end
%end
cnt = count / e
 perc = (cnt*100)/T

[Bruno Luong]

Unfortunately there is also a string of discussion that is disappear.

[John D'Errico]

@Hamad - you insult the people who gave you much time to answer your question, by making this question of no value to anyone else to ever read. You also make it less likely that those same people will bother to answer your future questions, by your action.

Please do not overwrite your question. This hurts the Answers site too.

[Hamad Gul]

John D'Errico

I am sorry but that was not my intention. You are right I shouldn't have cleared the question. I didn't understand how this page works but now I will restore it to make it helpful for future.

and for Stephen Cobeldick and Bruno Luong, by future I mean near future...

Not the future after 84 million years.

[Rena Berman]

(Answers Dev) Restored edit

Answer 1

[Bruno Luong]

You became real "Patient" now? Good! Then run this look at the screen and wait until it stops. If your type Ctrl C or kill MATLAB or reboot your PC, etc.., you must come back and change your claim ;-)

    seq_nchoosek(255,10); % function bellow
    while true
        c = seq_nchoosek(); % function bellow
        disp(c)
        if size(c,1)==0
            break
        end
        % ... do your stuff with c
    end

(Put function in seq_nchoosek.m mfile)

function v = seq_nchoosek(n,k)
% Sequential NCHOOSEK
% N and K non negative integers k <= n
% seq_nchoosek(n,k)     % reset the sequence of combination 
% v = seq_nchoosek()    % query the next combination
% 
% % Exemple of calling sequence:
%   seq_nchoosek(5,3)
%   while true
%       c = seq_nchoosek()
%       if size(c,1)==0
%           break
%       end
%       % ... do something with c
%   end
%
% See also: NCHOOSEK

persistent V S I K

if nargin >= 2
    % reset
    if ~(isscalar(n) && isscalar(k))
        error('seq_nchoosek: n and k must be scalars');
    end
    if k > n
        error('seq_nchoosek: k must be smaller or equal to n');
    end
    if n == 0
        V = [];
    else
        k = floor(k);
        n = floor(n);
        if n < 0 || k < 0
            error('seq_nchoosek: n and k must non negative integers');
        end
        V = 1:k; 
        I = k;
        K = k;
        S = V+(n-k);
    end
end
if nargout >= 1
    % query
    v = V;
    if size(V,1) > 0
        % move to next
        I = find(V-S,1,'last');
        if ~isempty(I)
            V(I) =  V(I)+1;
            V(I+1:K) =  V(I)+(1:K-I);
        else
            V = [];
        end
    end
end
end

[Muhammad Hamad]

Bruno Luong

Thanks a lot...

I will try this now and will post the result here

[Bruno Luong]

Sorry I certainly won't be here to check your post. ;-(

[Stephen23]

"I will try this now and will post the result here"

Our great-great-great-great-...-great grandchildren are looking forward to reading your post in about 80 million years or so.

[madhan ravi]

Probably this story will be read in an another planet.

[Vahid Hamdipoor]

@Bruno Luong Thank you so much. This is a great piece of code, And it solved my problem as well.