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

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."

Do you really need to obtain all of the subsets? Would a partial list suffice? E.g. subsets with at most n elements? Or subsets with between n and m elements? Or a "random" sampling of subsets? – DavidC Apr 16 '13 at 18:31
@rm-rf, on my system Developer$MaxMachineInteger is$2^{31}-1$, which is considerably smaller than the number of subsets. – Simon Woods Apr 16 '13 at 20:14 @SimonWoods Aaah... forgot about 32 bits :) Mine's 64 – R. M. Apr 16 '13 at 20:26 ## 2 Answers 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]  - +1 for the first half of the answer, but there is a much simpler way to generate the subsets, e.g. Array[Subsets[Range[3, 2300], {4}, {#}] &, {10}, 15831808]. Faster is to generate in blocks, e.g.: Subsets[Range[3, 2300], {4}, 1*^9 + {0, 9}] – Mr.Wizard Apr 16 '13 at 20:38 I am enthusiastically upvoting for two reasons: 1) TAOCP, 2) use of Goto – acl Apr 16 '13 at 20:42 @Mr.Wizard I needed this method in C once where unfortunately you don't have Subsets ;-) I prototyped it in Mathematica and I thought this is a good place to put it to show a use-case of a really nasty Goto/Label war. – halirutan Apr 16 '13 at 20:43 @Mr.Wizard, than you for your response. i will use your method. thanks.. – MATIRMAK Apr 16 '13 at 21:03 OP might probably be interested in some of the functions Combinatorica has, like... oh, I don't know, NextSubset[] or NextLexicographicSubset[]. – J. M. Apr 16 '13 at 23:52 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

This is False` on 64-bit Mathematica 9. Of course, building the resulting list of subsets will still be impracticable due to its huge size regardless of the theoretical possibility of doing so on a sufficiently large machine. – Oleksandr R. Apr 22 '13 at 4:33