How can I reduce memory-use on this combinatorics computation?

I have the following program:

m = 4;
N = 3;

a = [ones(N+m-1,1)' zeros(m,1)'];
b = perms(a);
c = unique(b,'rows');

d = [ones(length(c),1) c ones(length(c),1)];

a_powers = zeros(length(d(:,1)),1);
for i = 1:length(d(:,1))
    a_powers(i) = nnz(diff(d(i,:))==0);
end

[n_terms,which_power]=hist(a_powers',unique(a_powers'));

But my computer runs out of memory when I try m=5 and N=2, with the following error:

Out of memory. Type HELP MEMORY for your options.

Error in perms>permsr (line 53)
P = V(P);

Error in perms (line 26)
P = permsr(V);

I thought I could use nchoosek() or combnk(), but they didn't do what I wanted (to get all possible different combinations of a given number of ones and zeros in an array).

What can I do to optimize my program?

Thanks!

Answer 1

[John D'Errico]

clear
m = 5;
N = 2;
a = [ones(N+m-1,1)' zeros(m,1)'];

whos a
Name      Size            Bytes  Class     Attributes

a         1x11               88  double              

factorial(11)
ans =
    39916800

factorial(11)*11*8
ans =
   3.5127e+09

So you need at least 3.5 gigabytes of CONTIGUOUS FREE RAM to call perms here. Usually, you will need several times that, because temporary copies of arrays may be made along the way.

It is easy to generate small looking problems that are not in fact small, and your next question will surely be why your code exceeds available memory when m=6 and how to fix it.

[Frederik Faye]

I'm sorry, but what kind of an "answer" is this? You're merely stating that my program requires lots of RAM, when I already know that and my question is about what I can do to avoid this? Anyways, I found an answer on Stack Overflow: http://stackoverflow.com/questions/39182707/how-can-i-reduce-memory-use-on-this-combinatorics-computation/39183163#39183163

Answer 2

[Stephen23]

Don't calculate all permutations at once. Use nchoosek or perhaps one of the submissions on MATLAB File Exchange:

https://www.mathworks.com/matlabcentral/fileexchange/22692-nextperm

https://www.mathworks.com/matlabcentral/fileexchange/24459-next-combination-permutation

https://www.mathworks.com/matlabcentral/fileexchange/23067-oneperm