Hacker News Reader

Comment by enalicho | Hacker News Reader

Permutations and combinations already exist within the itertools module.

There is something deep about software that thwarts our dreams of making it re-usable, and makes debates about what primitives to put into the stdlib difficult. For one thing, it seems like we should be able to collectively determine a DAG of concepts, starting from simplest primitives and progressively building up derived concepts, like the tech tree in a game like Civilization, or Principia Mathematica. But that tree is so vast, and the most-useful points so sparse along it (ex: I don't think anyone's asking for Church numerals in their stdlib) that we end up debating which are the most-useful derived concepts to surface. Moreover, there's no language or compiler that is sufficiently smart to efficiently map all those concepts to the hardware we have, we instead go with expertly-wrought implementations.

To take this example, you _could_ count enumerations and permutations by passing a range(n) list to itertools and then counting how many actual results you get back, but that's silly when you could also just use the binomial theorem to get there directly. A compiler that could generally perform such transformations would be miraculous -- well beyond the territory of automated proof assistants like mathematica or gcc -O3 that trundle along cultivated routes of expert system rules, into the realm of actually discovering deep linkages at the frontier of our knowledge.

Until then it seems like stdlibs will just fracture along lines of strain among the userbase. Presumably, most Python users don't need anything beyond what a financial calculator would provide, and anyone else should head to numpy.

You make some good points. I've been in this field for almost 40 years -- I can remember a time when having a dedicated floating-point processor was seen as an unnecessary gimmick, only available at extra cost. Much has changed, and I think what constitutes a normal set of mathematical functions is changing as well, for a number of reasons:

1. Better math training in school.

2. More kinds of applied math problems being routinely evaluated by Python and other languages.

3. More available memory and storage capacity.

All of which argue for larger math libraries with more functions and classes of functions.

> Presumably, most Python users don't need anything beyond what a financial calculator would provide, and anyone else should head to numpy.

I would normally agree, but the argument has been made in this thread that numpy can't be installed in some environments -- environments that easily support Python, but that don't accommodate numpy without great difficulty.

> Permutations and combinations already exist within the itertools module.

Not exactly. Given argument lists, Itertools provides result lists (actually, iterators for that purpose) with the original elements permuted and combined, but doesn't provide numerical results for numerical arguments, as shown here: http://arachnoid.com/binomial_probability

I was referring to permutation and combination mathematical functions, not generator functions.

Put differently, you want the functions that count the number of permutations and combinations possible, not functions that yield/generate the actual permutations and combinations.

Yes, exactly, for a number of reasons including the problem of large arguments and results.

Hmm. Python has default Bignum promotion so the naive N choose K implementation will not suffer from overflow. I guess it could be slow for large values, but how many casual users need to calculate N choose K for large N?

Reply on news.ycombinator.com