[issue35431] The math module should provide a function for computing binomial coefficients

[kellerfuchs]

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 

___
___
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]

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 

___
___
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]

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 

___
___
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]

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 

___
___
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

[Steven D'Aprano]

Steven D'Aprano  added the comment:

On Fri, Dec 07, 2018 at 01:37:36PM +, Mark Dickinson wrote:

> I'd personally prefer that floats not be accepted;

Agreed. We can always add support for floats later, but its hard to 
remove it if it turns out to be problematic.

We ought to require n, r (or n, k) to be non-negative ints with 0 <= r 
<= n. Extending this to negative ints or floats is probably YAGNI, but 
if somebody does need it, they can request an enhancement in the future.

--

___
Python tracker 

___
___
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

[Steven D'Aprano]

Steven D'Aprano  added the comment:

> > 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. :-)

I think the key word there is *extend*. To the degree that any 
mathematical definition is "obvious", the obvious definition for number 
of combinations ("n choose r") is going to be 1 for r == 0 and 0 for r > n.

However, I think that it is too easy to get the order of n and r (n and 
k) mixed up, and write combinations(5, 10) when you wanted to choose 5 
from 10. I know I make that mistake on my calculator *all the time*, and 
so do my students, even with the nPr notation. So I recommend we raise 
ValueError for r > n.

--

___
Python tracker 

___
___
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

[Steven D'Aprano]

Steven D'Aprano  added the comment:

On Fri, Dec 07, 2018 at 12:04:44AM +, 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".

--

___
Python tracker 

___
___
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

[Mark Dickinson]

Mark Dickinson  added the comment:

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.

--

___
Python tracker 

___
___
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

[Mark Dickinson]

Mark Dickinson  added the comment:

@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?

--

___
Python tracker 

___
___
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

[Mark Dickinson]

Mark Dickinson  added the comment:

> 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.

--

___
Python tracker 

___
___
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

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

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

--

___
Python tracker 

___
___
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

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

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

--
nosy: +serhiy.storchaka

___
Python tracker 

___
___
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]

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 

___
___
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]

Change by kellerfuchs :


--
keywords: +patch
pull_requests: +10253
stage:  -> patch review

___
Python tracker 

___
___
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

[Mark Dickinson]

Mark Dickinson  added the comment:

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.

--

___
Python tracker 

___
___
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

[Mark Dickinson]

Mark Dickinson  added the comment:

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, 1 loops each)

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

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

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

--

___
Python tracker 

___
___
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

[Raymond Hettinger]

Raymond Hettinger  added the comment:

+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}

--
nosy: +mark.dickinson, rhettinger, tim.peters

___
Python tracker 

___
___
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]

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 

___
___
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

[Steven D'Aprano]

Steven D'Aprano  added the comment:

You import reduce but never use it :-)

+1 for this, I certainly miss it too.

--
nosy: +steven.daprano

___
Python tracker 

___
___
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]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com