Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  David Carraher Apr 16 '13 at 18:31
    
That is a lot of subsets, but it definitely is a machine integer... –  rm -rf Apr 16 '13 at 18:34
3  
Assuming each list takes one byte you need 1160942293126B~1081GB ... –  Spawn1701D Apr 16 '13 at 18:46
3  
@Nurettinırmak A list of 4 elements with your numbers takes 136 bytes. So for all the subsets, you'll need ~144 TB and change of memory. Good luck :) –  rm -rf Apr 16 '13 at 18:50
1  
@SimonWoods Aaah... forgot about 32 bits :) Mine's 64 –  rm -rf Apr 16 '13 at 20:26
show 9 more comments

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]
share|improve this answer
2  
+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
1  
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
add comment

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 *)
share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.