How can I find if the number of subsets for a list is very large?

Question

I'm trying to find the following;

Subsets[Range[2, 2300], {4}]

but my computer gave the following error:

Subsets::toomany: The number of subsets (1160942293126) indicated by «input» is too large; it must be a machine integer."

What is your advice?

Answer 1

Although this question is quite amusing, especially because of your I have 4GB. is it enough? comment, I think it is worth to give you some hints. Unfortunately, the number of subsets is so large, that even if you could create the subsets, it would be of no use because every calculation would need an incredible amount of time.

Let's say for simplicity you need all subsets of length 4 of Range[2300] then you would have to deal with Binomial[2300, 4] which is 1162964840675 subsets. Let's further assume you are a real deal in programming and your method needs only a millisecond to do whatever you like to do with each subset. The we still need about 35 years before you are done.

But to give you at least some advice, even if it will not help you with this problem. What you could do is go through all subsets instead of creating all at once. For this you only need an algorithm which can count through all subsets and on each subset you calculated what you need and step to the next.

One such algorithm can be found in Knuth's The Art of Computer Programming Vol. 4, Fascicle 3. This algorithm can just be written down. Here with the rarely used Mathematica functions Label and Goto ;-)

So if you want to see a walk through all 4-subsets of {0,...,99} you could do

LexicographicCombinations[t_Integer, n_Integer] := Module[
   {c = Table[i, {i, 0, t + 1}], j = t, x = 0},
   c[[t + 1]] = n;
   c[[t + 2]] = 0;
   Label[T2];
   result = c[[1 ;; -3]];
   If[j > 0, x = j; Goto[T6];];
   Label[T3];
   If[c[[1]] + 1 < c[[2]],
    c[[1]]++; Goto[T2],
    j = 2
    ];
   Label[T4];
   c[[j - 1]] = j - 2;
   x = c[[j]] + 1;
   If[x == c[[j + 1]],
    j++;
    Goto[T4];
    ];
   Label[T5];
   If[j > t, Return[]];
   Label[T6];
   c[[j]] = x;
   j--;
   Goto[T2];
   ];
Dynamic[result]
LexicographicCombinations[4, 100]

Answer 2

The number of subsets in your example is given by Binomial[2299, 4] and the largest machine integer on your system is Developer`$MaxMachineInteger, so a simple check if there are too many subsets is:

tooManySubsets = Binomial[2299, 4] > Developer`$MaxMachineInteger
(* True *)