all vectors of a specific dimension summing to a particular number with elements from {0,1}

This may be a number theory question, but I need to find ALL n-dimensional vectors(x_1,...,x_n) summing to j where each x_i is an element of {0,1}.

For example, for n=4 and j=2, then I need all possible ways x_1+x_2+x_3+x_4=2

Some cases that are apparent - (1, 1, 0, 0) or (1, 0, 1, 0). I need all such vectors for an arbitrary choice of n and j (including large values).

It would be nice if we could stack these vectors row by row in a matrix.

Any thoughts?

[the cyclist]

Can you be more specific by what you consider to be "large" n? You are quickly going to run into memory problems trying to store all possible vectors.

[superkevin2009]

n needs to be large, around 1000^2. Is this practical?

Answer 1

[the cyclist]

This will do it, but will have memory issues when n gets "large", for some value of large.

n = 4;
j = 2;

M = dec2bin(0:2^n-1)-'0';

M(sum(M,2)~=j,:) = []

Note that this code is terrible in some senses. It actually creates every combination that does not add up to your specified sum ... and then discards them.

I ran this code for n=26 and j=13. It took about 80 seconds to complete. The final matrix requires about 2GB of memory, and the algorithm temporarily allocated about 13 GB.

n=28 will attempt to create a matrix larger than the default maximum array size.

Answer 2

[Steven Lord]

How large are your "large values" and how much memory / time do you have?

The number of combinations are the total number of ways to select j items from n possibilities, or nchoosek(n, j). The list of indices is nchoosek(1:n, j).

inds = nchoosek(1:10, 5);
inds(77, :)
B = zeros(1, 10);
B(1, inds(77, :)) = 1 % One of the 252 candidates
C = zeros(1, 10);
C(1, inds(176, :)) = 1 % Another candidate, complementary to B

To determine how long it would take you to compute with each of those vectors at a rate of, say, 2 per second:

n = 20;
j = 10;
sec = seconds(nchoosek(n, j)/2);
hours(sec)

Depending on the values of n and j, you may want to convert seconds into minutes or years instead of hours.

[superkevin2009]

The problem is n needs to be large, around 1000^2 or larger, and I think these functions won't work when n gets that large. Any thoughts?

[Steven Lord]

Yes: rethink your approach for solving your problem. Let's see what would happen if j = 2.

>> years(seconds(nchoosek(1000^2, 2)))
ans =
        15844.3534090365

At one vector per second, you'd need over FIFTEEN THOUSAND YEARS to process them all. And how much memory would you need to store these as full logical arrays?

>> sz = [nchoosek(1000^2, 2), 1000^2];
>> numElements = prod(sz);
>> exabyte = numElements/(1024^6)
exabyte =
       0.433680435313333

You don't have that much memory available. Unless you have a machine with about 3% of Google's total storage capacity available to you.

With j = 3, you're looking at billions of years to process. I haven't checked how large j could be before you'd exceed the storage capacity of the observable universe, but I'm guessing maybe 4 or 5.

Answer 3

[John D'Errico]

You are kidding, right? You have vectors in 1000^2 = 1,000,000 dimensions? And you want to generate all possible such vectors with elements that sum to a given number, where the elements may be 0 or 1?

Even if the sum is only a very small number, you will find it impossible to generate all such possible vectors, with trillions upon trillions of possibilities. And of course, each vector is itself huge.

Computers have finite capabilities. They are not infinitely capable, infinitely fast, with infinitely much RAM. People get spoiled.

You need to find a different way to solve your problem. Or you need to start working on smaller problems. Even computing all possible vectors of length only 200 (NOT 100^2 but only 200) to find all possible vectors that sum for example to 100, will be an impossible task.

I mean, how hard could that be? How many possible ways are there to generate a sum of 100. Easy, right?

nchoosek(200,100)
Warning: Result may not be exact. Coefficient is greater than 9.007199e+15 and is only accurate to 15 digits 
> In nchoosek (line 92) 
ans =
      9.05485146561032e+58

Do you really understand how large of a number 9e58 is? For example, the mass of the entire earth is only roughly 6e27 grams. There are roughly only 1e50 atoms in the earth. So lets say that every atom in the earth was able to store ONE of those vectors of length 200. Some desktop supercomputer you have. Mine is not that good. It would fall short by a factor of roughly 1 billion. You would need a billion earths to store that much information.

Thats only for vectors of length 200. You are asking about something that is exponentially worse. If you have a computer that could store one bit of information per cubic picometer, in a space the size of the observable universe, it would be insufficient to solve your problem.

Just for kicks...

9.461e+15 meters in a light year. The visible universe is say 13 billion light years across. A picometer is 1e-12 meters.

(9.5e15*13e12*1e12)^3
ans =
          1.883652875e+123

It would be easy to swamp the capabilities of even that supercomputer with just a small such problem. You can want to do the impossible. Just don't expect to be successful. In this case, I hope you have a big budget for computer memory. And of course, a very fast computer.

[superkevin2009]

Actually, no. Should've been more specific and things are a bit simpler than that. See page 4 of this PDF. Trying to generate the constraint matrix for the transportation problem, which is a bunch of 0's and 1's.

https://www.utdallas.edu/~scniu/OPRE-6201/documents/TP1-Formulation.pdf

sum x_{ij} over i = c_j for every j sum x_{ij} over j = d_i for every i

[Walter Roberson]

If you have n variables each of which are to be set to 0 or 1, and the sum must be k, then the problem is equivalent to selecting k out of n marbles, and the number of ways to do that will be n!/(k!*(n-k)!), also known as (n Choose k).

Even using sparse matrices, you probably cannot afford the memory to list all of the possibilities out even for k as small as 4 (but you could probably afford it for k = 3).

If your problem requires you to construct all of the possibilities, then it is simply not practical to proceed in this way.

Are you trying to construct a problem in which you have a bunch of different sources and a bunch of sinks, and you are trying to figure out which source to associate with which sink? If so then constructing all of the possibilities is not a good way of solving such a problem.

[John D'Errico]

You WERE quite specific. You just have no concept of what it is that you are asking.

You claim to want to try to generate ALL n-dimensional vectors of length n=1000^2, subject to them meeting a sum constraint on the vector.

That is what my response points out the futility of. You don't have a big enough computer. You never will have a big enough computer to solve that problem for any sum greater than about 2.

Look at the number of solutions when the sum is only 3, nchoosek points out the answer.

nchoosek(1e6,3)
Warning: Result may not be exact. Coefficient is greater than 9.007199e+15 and is only accurate to 15 digits 
> In nchoosek (line 92) 
ans =
         1.66666166667e+17

1.66e17 is still a big number. One hundred sixty six quadrillion. If you intend to store all of those vectors in RAM, it will require

1.66e17*1e6*8
ans =
          1.328e+24

bytes of RAM. So on the order of a sexabyte of RAM. (I think I got the conversion right there.) A sexabyte of RAM is more memory than is on all of the RAM chips on all of the computers in the world today, combined. And that is just for a sum of 3. (Yes, I suppose if you used sparse matrices, the memory requirement will be smaller. Still an obscene amount though.)

[Walter Roberson]

You could encode it in 1.66e17 * 8 bytes by packing 3 twenty-bit indices into a 64 bit integer. That would only require 1.3 exabyte. That is probably more storage than Facebook has available, but it is less storage than Google has available.

3 shall be the number of thy counting

[Steven Lord]

Yes, but where would we be on one of my favorite Wikipedia pages by the time MATLAB finishes processing all those vectors?