Add a function for computing binomial coefficients to the math module

@tim-one

BPO	35431
Nosy	@tim-one, @rhettinger, @mdickinson, @jwilk, @stevendaprano, @serhiy-storchaka, @MojoVampire, @pablogsal, @KellerFuchs, @FR4NKESTI3N, @Radcliffe
PRs	bpo-35431: Add a function computing binomial numbers to the math module #11018 bpo-35431: Implemented math.comb #11414 bpo-35431: Refactor math.comb() implementation. #13725 bpo-37128: Add math.perm(). #13731 bpo-35431: Put math.comb() docs in correct place alphabetically #13734 bpo-35431: Drop the k <= n requirement #13798 bpo-35431: Fix grammar in docs #13801 bpo-35431: Simplify negativity checks in math.comb and math.perm. #13870 [3.8] bpo-35431: Simplify negativity checks in math.comb and math.perm. (GH-13870) #14125 bpo-35431: Test math.comb() and math.perm() for OverflowError only on CPython. #14146 [3.8] bpo-35431: Test math.comb() and math.perm() for OverflowError only on CPython. (GH-14146) #14226

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2019-06-05.14:38:26.241>
created_at = <Date 2018-12-06.21:18:02.072>
labels = ['type-feature', '3.8']
title = 'Add a function for computing binomial coefficients to the math module'
updated_at = <Date 2019-06-23.14:50:07.415>
user = 'https://github.com/KellerFuchs'

bugs.python.org fields:

activity = <Date 2019-06-23.14:50:07.415>
actor = 'serhiy.storchaka'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2019-06-05.14:38:26.241>
closer = 'rhettinger'
components = []
creation = <Date 2018-12-06.21:18:02.072>
creator = 'kellerfuchs'
dependencies = []
files = []
hgrepos = []
issue_num = 35431
keywords = ['patch']
message_count = 85.0
messages = ['331251', '331255', '331256', '331257', '331280', '331281', '331293', '331295', '331296', '331308', '331309', '331312', '331318', '331323', '331325', '331335', '331336', '331337', '331339', '331369', '331402', '331743', '331748', '331859', '332817', '332826', '332838', '332844', '332933', '332957', '332960', '332987', '332988', '332990', '334457', '334458', '334460', '334461', '334474', '334493', '334494', '334499', '334501', '334502', '334683', '334684', '336384', '336458', '336750', '342253', '342257', '344154', '344155', '344165', '344170', '344176', '344186', '344199', '344218', '344219', '344221', '344229', '344230', '344231', '344232', '344235', '344236', '344239', '344243', '344257', '344258', '344292', '344366', '344370', '344371', '344375', '344414', '344420', '344436', '344448', '344450', '344452', '344531', '345860', '346328']
nosy_count = 11.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'jwilk', 'steven.daprano', 'serhiy.storchaka', 'josh.r', 'pablogsal', 'kellerfuchs', 'FR4NKESTI3N', 'David Radcliffe']
pr_nums = ['11018', '11414', '13725', '13731', '13734', '13798', '13801', '13870', '14125', '14146', '14226']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue35431'
versions = ['Python 3.8']

A recuring pain point, for me and for many others who use Python for mathematical computations, is that the standard library does not provide a function for computing binomial coefficients.

I would like to suggest adding a function, in the math module, with the following signature:

binomial(n: Integral, k: Integral) -> Integral

A simple native Python implementation would be:

  from functools import reduce
  from math import factorial
  from numbers import Integral

  def binomial(n: Integral, k: Integral) -> Integral:
      if k < 0 or n < 0:
          raise ValueError("math.binomial takes non-negative parameters.")

      k = min(k, n-k)
      num, den = 1, 1
      for i in range(k):
          num = num * (n - i)
          den = den * (i + 1)

  return num//den

As far as I can tell, all of the math module is implemented in C, so this should be done in C too, but the implemented behaviour should be equivalent.

I will submit a Github pull request once I have a ready-to-review patch.

Not starting a PEP, per PEP-1:

Small enhancements or patches often don't need a PEP and can be injected into the Python development workflow with a patch submission to the Python issue tracker.

You import reduce but never use it :-)

+1 for this, I certainly miss it too.

Yes, that was a copypasta mistake (and I also import factorial needlessly) as the file I prototyped it in had some other code for testing my proposed implementation. :)

+1 I have wanted this a number of times.

FWIW, most recently I wrote it like this:

    def comb(n, r):
        'Equivalent to factorial(n) // (factorial(r) * factorial(n-r))'
        c = 1
        r = min(r, n-r)
        for i in range(1, r+1):
            c = c * (n - r + i) // i
        return c

I'm not sure is this is better than a single divide, but it kept the intermediate values from exploding in size, taking advantage of cancellation at each step.

Also, I'm not sure what the predominant choice for variable names should be, "n things taken r at a time" or "n things taken k at time".

Also, it's worth considering whether the function should be called "binomial", "choose", "combinations", or "comb". The word "binomial" seems too application specific but would make sense if we ever introduced a "multinomial" counterpart. The word "choose" is how we usually pronounce it. The word "combinations" fits nicely with the related counting functions, "combinations, permutations, and factorial". The word "comb" is short, works well with "perm" and "fact", and nicely differentiates itself as the integer counterparts of the combinatoric functions in the itertools module.

Wolfram uses both choose and Binomial[n,m]
SciPy uses comb(n, k).
Maple uses both numbcomb(n,m) and binomial(n,m).
TeX uses {n \choose k}

For some ranges of inputs, it may make sense to use the apparently naive implementation factorial(n) // factorial(k) // factorial(n - k). The current factorial implementation is significantly optimised, and using it directly may be faster than using an iterative solution.

Here are some timings (Python 3.7.1, macOS 10.13), using Raymond's comb function from msg331257:

In [5]: %timeit comb(1000, 600)
186 µs ± 442 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [6]: %timeit factorial(1000) // factorial(600) // factorial(400)
97.8 µs ± 256 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [7]: %timeit factorial(1000) // (factorial(600) * factorial(400))
91.1 µs ± 789 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

But that's just one set of inputs, on one system; your results may vary.

There's also the question of what inputs should be considered valid: binomial(n, k) for k > n should either return 0 or be a ValueError, but which? Same question for k < 0. There's a symmetry argument for allowing k < 0 if you allow k > n, but I can't think of pragmatic reasons to allow k < 0, while allowing k > n does seem potentially useful.

Note that this needs fixing with both of the code snippets shown so far: they both return 1 for k > n.

@Raymond

@Raymond Hettinger:

it's worth considering whether the function should be called "binomial", "choose", "combinations", or "comb"

Here goes the bike shed! :)
Kidding, this is a pretty important ergonomics/discoverability concern, and I hadn't given it much thought yet.

I'd rather not call it comb, because it collides with a completely-unrelated English word, and it's not obvious what it stands for unless one already knows.

The word "combinations" fits nicely with the related counting functions, "combinations, permutations, and factorial".

That's a good point; math.permutations doesn't exist, but itertools.permutations does, so I would expect (by analogy) a “combinations” functions to produce all possible k-sized subsets (rather than counting them), and that's exactly what itertools.combinations does.

On the other hand, combinations and permutations are names that make it perhaps more obvious what is being counted, so perhaps math.{combinations,permutations} should be aliases for math.{binomial,factorial} ? Is the name collision with itertools a problem?

TL;DR: “binomial” is more consistent with the current naming in math and itertools, but perhaps it makes sense to introduce math.{combination,permutations} as aliases?

(Note that I used math.binomial as the name in the PR so far, but that's only because I needed a name, not because I consider the discussion ended.)

@mark Dickinson:

The current factorial implementation is significantly optimised, and using it directly may be faster than using an iterative solution.

Yes, I avoided pushing specifically for a given algorithm (rather than getting upfront agreement on the functional behaviour) because the performance characteristics will likely be quite different once implemented in C in the math module.

(Unless I'm mistaken and there is a way to add pure-Python functions to the math module?)

binomial(n, k) for k > n should either return 0 or be a ValueError, but which?

From a mathematical standpoint, (n choose k) is defined for all non-negative k, n, with (n chooze k) = 0 when k>n or k=0.

It's necessary behaviour for the usual equations to hold (like (n + 1 choose k + 1) = (n choose k) + (n choose k + 1)).
As such, I'd argue that returning 0 is both more likely to be the thing the user wants (as in, it's necessary behaviour for combinatorics) and easier to reason about.

Negative k and n, on the other hand, should clearly be a ValueError, and so should non-integers inputs; this is consistent with factorial's behaviour.

I started a pull request and (for now) only added tests which document that (proposed) behaviour, so we can more easily discuss whether that's what we want.

Note that this needs fixing with both of the code snippets shown so far: they both return 1 for k > n.

Yes :)
I noticed last night, as I wrote Hypothesis tests for the snippet, but didn't think it was super important to send an updated version.

I think that it is better to add this function in a new module imath, which could contain other integer functions: factorial, gcs, as_integer_ration, isqrt, isprime, primes.

See https://mail.python.org/pipermail/python-ideas/2018-July/051917.html

Mathematically, binomial(n, k) for k > n is defined as 0.

Mathematically, binomial(n, k) for k > n is defined as 0.

It's not so clear cut. You can find different definitions out there. Knuth et. al., for example, in the book "Concrete Mathematics", extend the definition not just to negative k, but to negative n as well. Mathematicians aren't very good at agreeing on things. :-)

But that doesn't really matter: what we need to decide is what behaviour is useful for the users of the function.

@KellerFuchs

@KellerFuchs:

From a mathematical standpoint, (n choose k) is defined for all non-negative k, n, with (n chooze k) = 0 when k>n or k=0.

You don't mean the "k=0" part of that, right?

One more decision that needs to be made: should the new function accept integer-valued floats? Or should any float input give a TypeError.

I'd personally prefer that floats not be accepted; I think this was a misfeature of factorial that we shouldn't compound.

On Fri, Dec 07, 2018 at 12:04:44AM +0000, Raymond Hettinger wrote:

Also, I'm not sure what the predominant choice for variable names
should be, "n things taken r at a time" or "n things taken k at time".

Also, it's worth considering whether the function should be called
"binomial", "choose", "combinations", or "comb".

I've done a quick survey of some of the most common/popular scientific
calculators:

TI Nspire
TI-84 Plus
Casio Classpad
Casio FX-82AU Plus II

all call this nCr, and nPr for the permutation version. This matches
the notation taught in secondary school maths classes in Australia.
That's common and familiar notation for secondary school students, but
personally I'm not super-keen on it.

For what its worth, the colour I prefer for this bikeshed are "comb" and
"perm", which are the names used by the HP 48GX calculator. Second
choice would be to spell the names out in full, "combinations" and
"permutations".

I'm going to repeat part of an earlier comment :-)

"""
Please resist pointless feature creep. The original report was about comb(n, k) for integer n and k with 0 <= k <= n and that's all. Everyone who commented appeared to agree they'd find that useful.
"""

Why can't we take universal agreement for an initial answer? ;-)

Looking at what other packages do doesn't really interest me, unless they differ on the cases everyone agreed would be useful - they have different audiences than Python has. Guess what Wolfram returns for

(-4) choose (-5)

Go ahead. That's right: -4. Sheesh - I don't care who their audience is, any code calling choose with those arguments would be far better served if the function complained.

I understand that pure mathematics is not the primary use case. But I would
expect that math.comb() would be used to implement mathematical formulas.
As a simple example, the number of edges in a complete graph on n vertices
is binomial(n, 2), and this should be valid if n < 2. Polynomial
interpolation is another problem where this can occur. However, I do agree
that binomial coefficients with negative arguments are relatively
unimportant.

On Sun, Jun 2, 2019 at 8:59 PM Raymond Hettinger <[email protected]>
wrote:

Raymond Hettinger <[email protected]> added the comment:

Here are a few other data points. There is no consensus but either
returning 0 or erroring out seem reasonable.

MS Excel's COMBIN: If number < 0, number_chosen < 0, or number <
number_chosen, COMBIN returns the #NUM! error value.

Scipy.misc.comb: If k > N, N < 0, or k < 0, then a 0 is returned.

Matlib.nchoose: Error: K must an integer between 0 and N.

Maple.numbcomb: Unclear from the docs what this does

Wolfram alpha: Returns 0
https://www.wolframalpha.com/input/?i=10+choose+12

----------

Python tracker <[email protected]>
<https://bugs.python.org/issue35431\>

I'm not fatally opposed to relaxing k <= n. David makes some good points about it, and - as Raymond already noted - "0" is consistent with the behavior of itertools.combinations().

The docs would need to change, though, because the factorial "definition" would no longer make sense. Defining it in terms of the falling factorial would, but that's too obscure for Python's audience. Probably a combinatorial definition would be best: `comb(n, k) is the number of k-element subsets of an n-element set". Then it's clear that n and k are cardinals (integers >= 0), and that the result is 0 when k > n.

For what its worth, there are concrete, practical applications for
binomial coefficients with negative arguments. They are used in
fractional calculus

https://nrich.maths.org/1365

which in turn has applications in physics, chemistry and other sciences:

https://en.wikipedia.org/wiki/Fractional_calculus#Applications

Take that however you see fit :-)

My own preference is for a comb() function that returns 0 for out of
bounds values (e.g. "choose 5 items from 4"), and a seperate binomial()
function that accepts any positive or negative integer values. Even I
think that fractional and complex arguments are probably a bit too
exotic for the std lib -- that's Mathematica territory.

And yes, Mathematica does accept fractional and complex arguments to
the choose() function.

https://www.wolframalpha.com/input/?i=choose%28sqr%28-3.5%29,+sqrt%28-4%2Bi%29%29

Given that (a) we're right up against feature freeze, and (b) the discussions about API already happened in plenty of good time some months ago, leading to agreement on the initial API, I think we should avoid any last-minute changes and stick with what we have for 3.8. Then we can have a more relaxed discussion about what, if anything, should be changed for 3.9.

I don't have a preference one way or the other (both ways have plausible arguments, error checking vs utility beyond simple combinatorics, and both ways have ample precedents).

That said, if we're going to ultimately relax the constraints, it would be better to do it now before the API is released.

Even if we were already in feature freeze, it would be okay to change it (the purpose of a beta is to elicit end-user feedback which is what David has just given).

Python needs a benevolent dictator ;-)

I'd be happy for Mark, Raymond, or me to play that role here. If it were me, I'd drop the k <= n requirement: both arguments must be non-negative integers. Because a combinatorial (not factorial-, and certainly not gamma-, based) definition of comb() is best suited for Python's general audience, and "number of ways to pick k things out of n without regard to order" makes clear sense for any pair of non-negative k and n. But anything beyond that does not.

If it were me, I'd drop the k <= n requirement

+1 from me.

Fine by me. The same change should be applied to math.perm.

New changeset 963eb0f by Raymond Hettinger in branch 'master':
bpo-35431: Drop the k <= n requirement (GH-13798)
963eb0f

New changeset 1b8a46d by Serhiy Storchaka in branch 'master':
bpo-35431: Test math.comb() and math.perm() for OverflowError only on CPython. (GH-14146)
1b8a46d

New changeset 914d6b7 by Serhiy Storchaka in branch '3.8':
[3.8] bpo-35431: Test math.comb() and math.perm() for OverflowError only on CPython. (GH-14146) (bpo-14226)
914d6b7

Navigation Menu

Repository navigation

Add a function for computing binomial coefficients to the math module #79612

63 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Add a function for computing binomial coefficients to the math module #79612

Description

Activity

KellerFuchs commented on Dec 6, 2018

stevendaprano commented on Dec 6, 2018

KellerFuchs commented on Dec 6, 2018

rhettinger commented on Dec 7, 2018

mdickinson commented on Dec 7, 2018

mdickinson commented on Dec 7, 2018

KellerFuchs commented on Dec 7, 2018

serhiy-storchaka commented on Dec 7, 2018

serhiy-storchaka commented on Dec 7, 2018

mdickinson commented on Dec 7, 2018

mdickinson commented on Dec 7, 2018

mdickinson commented on Dec 7, 2018

stevendaprano commented on Dec 7, 2018

63 remaining items

tim-one commented on Jun 3, 2019

Radcliffe commented on Jun 3, 2019

tim-one commented on Jun 3, 2019

stevendaprano commented on Jun 3, 2019

mdickinson commented on Jun 3, 2019

rhettinger commented on Jun 3, 2019

tim-one commented on Jun 3, 2019

rhettinger commented on Jun 3, 2019

mdickinson commented on Jun 3, 2019

rhettinger commented on Jun 4, 2019

serhiy-storchaka commented on Jun 17, 2019

serhiy-storchaka commented on Jun 23, 2019

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions