On Wednesday, 19 March 2014 at 01:29:16 UTC, bearophile wrote:
I suggest a Phobos module named "combinatorics" (or just
"combs"?). It's not meant to be a complete library of
combinatorics algorithms, nor to contain the most optimized
algorithms around. It's meant to be a collection of efficient
but sufficiently short implementations of the few
algorithms/ranges you need most often. Everything else,
including the most efficient code, I my opinion should be left
to specialized numerical libraries external to Phobos (or could
be added later if Phobos gains more developers).
I think the most commonly useful functions are:
- A lazy range (a simple unbounded segmented Sieve) that
generates primes numbers very quickly, in a given range, or
from 2;
- A isPrime() function. Probably it should cache some of its
computations.
- A function to compute the GCD on ulongs/longs/bigints is
useful.
(Issues 4125 and 7102).
- An efficient and as much as possibly overflow-safe
binomial(n,k) that returns a single number.
I'd also like permutations/combinations/pairwise ranges (Phobos
already has a permutations, but it's designed on the legacy C++
style of functions, so it's not good enough).
(See ER issue 6788 for pairwise. A the moment I can't find my
Bugzilla ER entry for permutations/combinations, but you can
see the good API for the permutations/combinations ranges in
the code I have written here:
http://rosettacode.org/wiki/Permutations#Fast_Lazy_Version See
also the good API of the Python combinations/permutations here:
http://docs.python.org/3/library/itertools.html#itertools.permutations
note also the useful "r" and "repeat" arguments).
With such 7 functions/ranges you can do lot of things :-)
Bye,
bearophile
I've wanted exactly this. I was doing the euler project problems
and had to implement my own prime sieve, isPrime range, GCD,
binomial, and combination function (I used Phobos' permutation
function, but was a bit disappointed that it wasn't implemented
as a range). Being familiar with the Python
combinations/permutations functions, I was looking for similar
functionality in Phobos and was sad to find it missing. So +1 for
a combinatorics module, and for a numerical/prime module.
