[issue35431] Add a function for computing binomial coefficients to the math module
kellerfuchs added the comment: > Given that people clarified they prefer comb(), and that people conspicuously > didn't comment on it being entirely-opaque to people who do not elready know > what it is, I guess there is indeed consensus. commit afb3d36e82b8d690a410fa9dca8029a8fad42984 Author: The Fox in the Shell Date: Fri Feb 1 15:42:11 2019 +0100 Rename math.combinations to math.comb -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] Add a function for computing binomial coefficients to the math module
kellerfuchs added the comment: @Steven > > This involved a few changes, which seem to reflect the consensus here: > > - raise ValueError if k>n ; > > - rename the function to math.combinations. > [...] > > As far as I can tell from the discussions here, Steven and you stated a > > preference for the shortened names, and that's it. > > There was also no reply to my comment about `comb` being confusing (due to > > the collision with an English word). > > > > Since there was, however, pretty clear agreement on calling it after > > combinations (shortened or not) rather than binomial(), I went with this. > > I see at least four people (myself, Raymond, Mark and Tim) giving comb as first choice, and I didn't see anyone give combinations as their first choice. > > I don't object to you taking it upon yourself to go with the longer name > (which is my second choice), but I do object to you claiming concensus I wasn't claiming consensus on the short-vs.-long name issue, but on the binomial-vs-combinations one. I thought that would have been clear considering the context quoted above (which was missing from your reply) Given that people clarified they prefer comb(), and that people conspicuously didn't comment on it being entirely-opaque to people who do not elready know what it is, I guess there is indeed consensus. -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] Add a function for computing binomial coefficients to the math module
kellerfuchs added the comment: @Raymond Hettinger > Let's name this comb() instead of binomial() please (as requested by me, > Mark, and Tim). (Replying here to keep the discussion in a single place.) As far as I can tell from the discussions here, Steven and you stated a preference for the shortened names, and that's it. There was also no reply to my comment about `comb` being confusing (due to the collision with an English word). Since there was, however, pretty clear agreement on calling it after combinations (shortened or not) rather than binomial(), I went with this. -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] Add a function for computing binomial coefficients to the math module
kellerfuchs added the comment: So, I rebased Yash's and my branches, and merged them together. The result is still in PR#11018. This involved a few changes, which seem to reflect the consensus here: - raise ValueError if k>n ; - rename the function to math.combinations. -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] Add a function for computing binomial coefficients to the math module
kellerfuchs added the comment: > Start with an initial patch that implements this simplest possible > implementation, accompanied by clean documentation and thorough testing. > > Once everyone has agreed on the API (i.e. calling it "comb()", how to handle > various input datatypes, and handling of corner cases), and the patch is > applied, only then turn to a second pass for optimizations +1 from me on that. @Yash: Thanks a bunch for starting on the implementation. I will have a look shortly :) -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] Add a function for computing binomial coefficients to the math module
kellerfuchs added the comment: Hi everyone, Sorry for the lack of reply, I severely underestimated how exhausting the holiday season would be. Catching up with the comments right now. -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] The math module should provide a function for computing binomial coefficients
kellerfuchs added the comment: @Steven D'Aprano: > 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. It's also not universal; in my experience, most calculators are localized for a given market, and may use different notations (in particular, the notation for combinations/binomial numbers changes across countries). -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] The math module should provide a function for computing binomial coefficients
kellerfuchs added the comment: > I'd personally prefer that floats not be accepted; I think this was a > misfeature of `factorial` that we shouldn't compound. OK; I only went with that because I assumed there were Good Reasons© that factorial did it, but if rejecting integral floats isn't going to be a controversial move I'm also in favor of it. Updating the PR momentarily to check that binomial rejects floats. -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] The math module should provide a function for computing binomial coefficients
kellerfuchs added the comment: @Mark Dickinson: > You don't mean the "k=0" part of that, right? Indeed not; the tests in the PR actually assert binomial(n, n) == binomial(n, 0) == 1. -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] The math module should provide a function for computing binomial coefficients
kellerfuchs added the comment: @Serhiy Storchaka: > I think that it is better to add this function in a new module imath, which > could contain other integer functions imath is a fine idea, and you already started a discussion in python-ideas@, but it's a much bigger undertaking than just adding this one function, and you can move it there once imath happens. As such, I think it's out-of-scope in this issue. -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] The math module should provide a function for computing binomial coefficients
kellerfuchs added the comment:
@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.
--
___
Python tracker
<https://bugs.python.org/issue35431>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] The math module should provide a function for computing binomial coefficients
Change by kellerfuchs : -- keywords: +patch pull_requests: +10253 stage: -> patch review ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] The math module should provide a function for computing binomial coefficients
kellerfuchs added the comment: 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. :) -- ___ Python tracker <https://bugs.python.org/issue35431> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35431] The math module should provide a function for computing binomial coefficients
New submission from kellerfuchs :
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.
[PEP 1]: https://www.python.org/dev/peps/pep-0001/#id36
------
messages: 331251
nosy: kellerfuchs
priority: normal
severity: normal
status: open
title: The math module should provide a function for computing binomial
coefficients
type: enhancement
versions: Python 3.8
___
Python tracker
<https://bugs.python.org/issue35431>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
