title: counting combinations and permutations efficiently
body: <p>I have some code to count permutations and combinations, and I'm trying to make it work better for large numbers.</p>
  
  <p>I've found a better algorithm for permutations that avoids large intermediate results, but I still think I can do better for combinations.</p>
  
  <p>So far, I've put in a special case to reflect the symmetry of nCr, but I'd still like to find a better algorithm that avoids the call to factorial(r), which is an unnecessarily large intermediate result. Without this optimization, the last doctest takes too long trying to calculate factorial(99000).</p>
  
  <p>Can anyone suggest a more efficient way to count combinations?</p>
  
  <pre><code>from math import factorial
  
  def product(iterable):
      prod = 1
      for n in iterable:
          prod *= n
      return prod
  
  def npr(n, r):
      """
      Calculate the number of ordered permutations of r items taken from a
      population of size n.
  
      &gt;&gt;&gt; npr(3, 2)
      6
      &gt;&gt;&gt; npr(100, 20)
      1303995018204712451095685346159820800000
      """
      assert 0 &lt;= r &lt;= n
      return product(range(n - r + 1, n + 1))
  
  def ncr(n, r):
      """
      Calculate the number of unordered combinations of r items taken from a
      population of size n.
  
      &gt;&gt;&gt; ncr(3, 2)
      3
      &gt;&gt;&gt; ncr(100, 20)
      535983370403809682970
      &gt;&gt;&gt; ncr(100000, 1000) == ncr(100000, 99000)
      True
      """
      assert 0 &lt;= r &lt;= n
      if r &gt; n // 2:
          r = n - r
      return npr(n, r) // factorial(r)
  </code></pre>