Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 4 down vote favorite
1

Sometimes I want to do an exact test by examining all possible combinations of the data to build an empirical distribution against which I can test my observed differences between means. To find the possible combinations I'd typically use the combn function. The choose function can show me how many possible combinations there are. It is very easy for the number of combinations to get so large that it is not possible to store the result of the combn function, e.g. combn(28,14) requires a 2.1 Gb vector. So I tried writing an object that steped through the same logic as the combn function in order to provide the values off an imaginary "stack" one at a time. However, this method (as I instantiated it) is easily 50 times slower than combn at reasonable combination sizes, leading me to think it will also be painfully slow for larger combination sizes.

Is there a better algorithm for doing this sort of thing than the algorithm used in combn?Specifically is there a way to generate and pull the Nth possible combination without calculating through all previous combinations?

share|improve this question
Has anyone noticed that the number of questions that should be in StackOverflow R rocketed up here recently? – John Aug 5 '10 at 5:32
1  
Why not making random sampling? – mbq♦ Aug 5 '10 at 7:21
3  
@John: If you feel that way discuss the issue at meta.stats.stackexchange.com/questions/248/…, no need to be snarky. – Russell S. Pierce Aug 5 '10 at 7:59
@mbq: Random sampling will quickly provide a reasonable approximate, especially with well behaved data. However, I did specify that my goal was an exact test. – Russell S. Pierce Aug 5 '10 at 8:04
@drknexus That's why it was a comment not an answer. – mbq♦ Aug 5 '10 at 9:19
show 2 more comments

2 Answers

up vote 3 down vote accepted

If you wish to trade processing speed for memory (which I think you do), I would suggest the following algorithm:

  • Set up a loop from 1 to N Choose K, indexed by i
  • Each i can be considered an index to a combinadic, decode as such
  • Use the combination to perform your test statistic, store the result, discard the combination
  • Repeat

This will give you all N Choose K possible combinations without having to create them explicitly. I have code to do this in R if you'd like it (you can email me at mark dot m period fredrickson at-symbol gmail dot com).

share|improve this answer
Here is a post with the code and some illustrations: markmfredrickson.com/thoughts/2010-08-06-combinadics-in-r.html – Mark M. Fredrickson Aug 6 '10 at 23:50
I'm accepting this answer because it solves (what I think) is the harder of the problems I was looking for a solution to - picking a particular combination out without calculating the preceding values. Unfortunately, it is still very slow. Perhaps as mentioned here and elsewhere a binary search would help speed things up. Perhaps the best approach is to have one thread generating the combinations stepwise as in mbq's answer and another thread reading them off and testing them. – Russell S. Pierce Aug 12 '10 at 7:15
up vote 0 down vote

Generating combinations is pretty easy, see for instance this; write this code in R and then process each combination at a time it appears.

share|improve this answer
But will this cope with very large combinations? – csgillespie Aug 5 '10 at 10:40
@csgillespie Well, I believe so -- it works in situ, so only one combination is stored in memory at a time, and the results of simulation can be also aggregated to eliminate the need of storing them. This will of course work terribly long, but exhaustive searches usually do. For speed it could be written in C, but then along with the simulation part, which probably is way slower than a generator step. – mbq♦ Aug 5 '10 at 11:11
2  
That looks almost identical to how R's combn function is already doing things. I wrote up a version of combn that does take combinations off the stack one at a time, and as mbq says because it is only storing one combination in memory at a time it can handle very large combinations. The problem with doing it in R is that doing a step-by-step approach in a function typically involves reading the state variables into the function, manipulating them, then storing them back out to global - which seems to just slow everything /way/ down. – Russell S. Pierce Aug 5 '10 at 15:34

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.