title: My algorithm for choosing k element subset to handle huge number in C#
body: <p>I am writing the algorithm which is choosing a subset (of k elements) from a set (of n elements).</p>
  
  <p>I have accomplished the task with a success. It works fine for small numbers.
  I have tested it for n=6, k=3 and n=10, k=5.</p>
  
  <p>The problem is starting now, when I need to use it for huge numbers.
  Sometimes I would need to use it for let's say n = 96000000 and k = 3000.
  To simply testing a bit, lets focus on example for n = 786432 and k = 1000. Then there is 461946653375201 such a possibilities. As the third parameters to my function there is rank number, so the number for particular unique subset. Let's try few random, for example 3264832 works fine (gave me subset of different numbers), but for 4619466533201 the one number (in subset) is repeated several times, what is wrong. It must be set as well subset based on unique numbers !</p>
  
  <p>Question is to make it works correct and what is the problem ? The numbers are too big even for ulong ?</p>
  
  <p>If you have any question feel free to ask.</p>
  
  <p>Here is my code:</p>
  
  <pre><code>    public static ulong BinomialCoefficient(ulong N, ulong K)
      {
          ulong result = 1;
          for (ulong i = 1; i &lt;= K; i++)
          {
              result *= N - (K - i);
              result /= i;
          }
          return result;
      }
  
      public static ulong[] ChooseSubsetByRank(ulong sizeOfSet, ulong sizeOfSubset, ulong rank)
      {
          ulong[] resultingSubset = new ulong[sizeOfSubset];
          ulong x = sizeOfSet;
  
          for (ulong i = sizeOfSubset; i &gt; 0; i--)
          {
              while (BinomialCoefficient(x, i) &gt; rank)
                  x--;
  
              resultingSubset[i - 1] = x + 1;
              rank = BinomialCoefficient(x + 1, i) - rank - 1;
          }
  
          return resultingSubset;
      }
  </code></pre>
  
  <p>And below is the run code. To test it you may change the third argument at the line below.</p>
  
  <pre><code>        ulong[] arrayTest = Logic.ChooseSubsetByRank(786432, 1000, 4619466533201);
          string test = "";
          for (int i = 0; i &lt; arrayTest.Length; i++)
              test = test + arrayTest[i].ToString() + " ";
          System.Windows.MessageBox.Show(" " + test);
  </code></pre>