Devin Teske
2019-Dec-06 00:09 UTC
[FreeBSD-Announce] BSD-Licensed Combinatorics library/utility
Hello. I?d like to announce a new utility/library for FreeBSD base available for review. https://reviews.freebsd.org/D16132 <https://reviews.freebsd.org/D16132> Preview HTML-formatted manuals: https://fraubsd.org/doc/cmb.1.html <https://fraubsd.org/doc/cmb.1.html> https://fraubsd.org/doc/cmb.3.html <https://fraubsd.org/doc/cmb.3.html> *** Combinatorics is the study of combinations. For example, calculating how many possible combinations given a set of items and some parameters such as how many or a range of how many items to select. Iterating over every possible combination to perform some action for each ? with support for position indicators so that if you prematurely terminate you can pick up at the last combination where you left-off. Find combinations of numerical items that produce a particular sum, quotient, product, or difference. *** While these problem have been solved (or partially solved) in languages such as: Perl (Algorithm::Combinatorics) Python (itertools, numpy) R (comb) Haskell Others ? my implementation is faster than all of them. ? and BSD-licensed. ? and written in C with bindings for Perl and Python (R and others forthcoming). ? and works on Mac OS X, Linux, Solaris, BSD, etc. with minimal dependencies. NB: The Perl/Python bindings are not in the review for import to base. *** Q. Why add this to FreeBSD base? A. Lofty goals With a combinatorics library, we can start thinking about taking on monumental tasks such as: * Making the ?build option survey? test all combinations of build options Today, the build-option survey only iterates over a handful of hand-selected build options. It does combinatorially iterate over all possible combinations as that might prove exorbitantly expensive in either time or resources. I will be attempting to solve the incompleteness aspect using cmb, while dedicating several hundred cores in a private cluster to solving the time/resource requirements. * Offer packages compiled from ports with non-standard options I don?t know if any other Operating System is tackling this problem, but I think we can, if not for the entire ports tree, a subset thereof. One of the things I imagine is adding to the ports tree, the ability to say ?make allpkg? or something which would compile every possible combination of optional directives in the given port directory where you say it, generating uniquely named packages with appropriately codified MANIFEST files that enumerate which options were enabled for each. This project too, I am not sure how many resources or time will need to be dedicated to staying current (especially if we try and tackle the entire ports tree), but I do happen to have quite a lot of hardware at my disposal and HPC scheduling software providing an MPI environment to get the job done. *** Through both of these endeavors, the missing element has been a permissively-licensed high-performance combinatorics library. I first started working in the highly specialized area of mathematics dealing with combinations back in 1989, wrote my first Proof-of-Concept (using Bourne Shell of all things) back in 2001 and in the past 3 years have made a concerted effort to provide the missing aspect to more complex work like the above endeavors. 30 years in the making, I am excited to bring to FreeBSD base my BSD-licensed solution. Let it be like ?seq?, ?jot?, and other well-known utilities in base for solving a hard problem in the ?UNIX Way?? (write a tool to do one job and do it well). ? Cheers, Devin