title: Fastest solution for all possible combinations, taking k elements out of n possible with k>2 and n large
body: <p>I am using MATLAB to find all of the possible combinations of <em>k</em> elements out of <em>n</em> possible elements. I stumbled across <a href="https://stackoverflow.com/questions/28506232/fastest-solution-to-list-all-pairs-of-n-integers">this question</a>, but unfortunately it does not solve my problem. Of course, neither does <a href="http://www.mathworks.com/help/matlab/ref/nchoosek.html" rel="nofollow noreferrer"><code>nchoosek</code></a> as my <em>n</em> is around 100.</p>
  
  <p>Truth is, I don't need all of the possible combinations at the same time. I will explain what I need, as there might be an easier way to achieve the desired result. I have a matrix <em>M</em> of 100 rows and 25 columns. </p>
  
  <p>Think of a submatrix of <em>M</em> as a matrix formed by ALL columns of <em>M</em> and only a subset of the rows. I have a function <em>f</em> that can be applied to any matrix which gives a result of either -1 or 1. For example, you can think of the function as <code>sign(det(A))</code> where <em>A</em> is any matrix (the exact function is irrelevant for this part of the question).</p>
  
  <p>I want to know what is the biggest number of rows of <em>M</em> for which the submatrix <em>A</em> formed by these rows is such that <em>f(A) = 1</em>. Notice that if <em>f(M) = 1</em>, I am done. However, if this is not the case then I need to start combining rows, starting of all combinations with 99 rows, then taking the ones with 98 rows, and so on.</p>
  
  <p>Up to this point, my implementation had to do with <a href="http://www.mathworks.com/help/matlab/ref/nchoosek.html" rel="nofollow noreferrer"><code>nchoosek</code></a> which worked when <em>M</em> had only a few rows. However, now that I am working with a relatively bigger dataset, things get stuck. Do any of you guys think of a way to implement this without having to use the above function? Any help would be gladly appreciated.</p>
  
  <p>Here is my minimal working example, it works for small <code>obs_tot</code> but fails when I try to use bigger numbers:</p>
  
  <pre><code>value = -1; obs_tot = 100; n_rows = 25;
  mat = randi(obs_tot,n_rows);
  while value == -1
      posibles = nchoosek(1:obs_tot,i);
      [num_tries,num_obs] = size(possibles);
      num_try = 1;
          while value == 0 &amp;&amp; num_try &lt;= num_tries
          check = mat(possibles(num_try,:),:);
          value = sign(det(check));
          num_try = num_try + 1;
          end
      i = i - 1;
  end
  obs_used = possibles(num_try-1,:)';
  </code></pre>