Abacus

Computer Algebra System for Symbolic Computations for Combinatorics and Algebraic Number Theory for JavaScript and Python

version 2.0.0 almost complete (407 kB minified)

Abacus is a relatively small and versatile computer algebra and symbolic computation system containing methods and math utilities for fast combinatorial object computation and algebraic / number theoretic computation. It builds on, and extends, a deprecated previous project Simulacra.

Contents

• Live Playground Example
• Online REPL
• Combinatorial and Number Theory Examples
• Features
• Performance
• Credits and References
• Example API
• Todo

Features

Supports: (see: test/test.bat)

Combinatorics:

• Tensor (test/tensors.js)

• Tuple (test/tuples.js)

• Permutation (test/permutations.js, test/permutations-bigint.js)

• CyclicPermutation (test/cyclic_permutations.js)

• MultisetPermutation (test/multiset_permutations.js)

• DerangementPermutation (test/derangements.js)

• InvolutionPermutation (test/involutions.js) supported order is LEX of swaps

• ConnectedPermutation (test/connected_permutations.js) supported order is LEX of cycle

• UnorderedCombination / Combination (test/combinations.js)

• OrderedCombination / Variation / kPermutation (test/ordered_combinations.js)

• UnorderedRepeatedCombination / RepeatedCombination (test/combinations_repeats.js)

• OrderedRepeatedCombination / RepeatedVariation / kTuple (test/ordered_combinations_repeats.js)

• Subset (test/subsets.js)

• Partition (test/partitions.js) partial support for COLEX

• Composition (test/compositions.js) partial support for COLEX

• RestrictedPartition (test/restricted_partitions.js) partial support for COLEX

• RestrictedComposition (test/restricted_compositions.js) partial support for COLEX

• SetPartition (test/setpartitions.js) rank/unrank methods missing, only LEX/REVLEX order

• RestrictedSetPartition (test/setpartitions.js) exactly K #parts, rank/unrank methods missing, only LEX/REVLEX order

• CatalanWord (eg balanced parentheses) (test/paren.js) rank/unrank methods missing

• LatinSquare (test/latin_squares.js)

• MagicSquare (test/magic_squares.js)

• algebraic composition and sequences of combinatorial objects to construct new combinatorial objects (eg all combinations = all permutations OF all unique combinations, see test/permutations_of_combinations.js and test/permutations_of_permutations.js, k-Derangements = (n,k) Combinations combined With (n-k) Derangements, see test/k-derangements.js or all subsets = (n,0)Combinations + (n,1)Combinations + .. + (n,n-1)Combinations + (n,n)Combinations, see test/combination_subsets.js)

• custom and built-in filters which can select and generate any custom and complex combinatorial object from filtering other combinatorial objects as efficiently as possible (e.g see test/filtered.js, test/filtered_partitions.js). Also algebraic / boolean composition of filters (i.e .NOT(), .AND(), .OR() and so on..). Note that filtering should be used with caution and only if no other method is currently possible to generate the desired combinatorial object as filtering is equivalent to exhaustive search over the space of the original combinatorial object and as such can be an inefficient way to generate a combinatorial object (e.g see test/filtered.js). Note2 with filtering applied some methods like .total(), .hasNext() still return data of the original object not the filtered object since that would require to pre-generate all the data and filter them afterwards instead of doing it one-by-one on each generation and would be impractical and unachievable for very large combinatorial objects, so be careful when using, for example, .total() with fitering applied

• multiple (combined) iterator orderings & traversals: lex, colex, random, reversed, reflected, minimal (not implemented yet). For example: "revlex" (equivalent to "lex,reversed"), "refcolex" (equivalent to "colex,reflected"), and so on..

• arbitrary range of combinatorial objects in a number of supported orderings (ie lex, colex, random,..) (and with filtering applied, if set). Note unrank methods have to be implemented for this feature to work

• efficient and unbiased generation, (un)ranking, succession & random methods for supported combinatorial objects (see below)

Symbolic Computations:

• Numbers, eg fibonacci, catalan, bell, factorial, partition, polygonal, .. (test/numbers.js)

• Number Theory Functions, eg gcd / xgcd / polygcd / polyxgcd / groebner, divisors, moebius, legendre, jacobi, isqrt, ikthroot, .. (test/number_theory.js)

• Integer, Rational, Complex supporting arbitrary precision arithmetic (test/integers.js, test/rationals.js, test/complex.js)

• Polynomial, MultiPolynomial univariate / multivariate with coefficients from a Ring/Field (test/polynomials.js, test/multivariate.js)

• RationalFunc Rational functions as fractions of multivariate polynomials (test/ratfuncs.js)

• Algebraic Rings and Fields eg. Ring.Z(), Ring.Q(), Ring.C(), Ring.Q("x","y"), .. (test/polynomials.js, test/multivariate.js, test/rings.js)

• Matrix with coefficients from a Ring/Field (test/matrices.js)

• Expr general Symbolic Expressions (test/expressions.js)

• Progression (Infinite, Arithmetic, Geometric) (test/progressions.js)

• PrimeSieve, Primality Tests, Prime Factorisation (test/primes.js)

• Diophantine Linear Equations, Linear Congruences, Pythagorean n-Tuples (test/diophantine.js)

• Linear Systems, Polynomial Systems, Linear Inequalities (test/linears.js, test/polys.js, test/lineqs.js)

• big-integer arithmetic, PRNGs and other math utilities are pluggable using external implementations, making the lib very flexible especialy with respect to handling big-integers & (pseudo-)random number generators (examples use the excellent BigInteger.js)

Performance

• first/last, random, rank/unrank methods use efficient linear O(n) (or log-linear O(nlgn)) time and space algorithms (note a couple of rank/unrank methods are of O(n^2) or higher order)
• random methods are statistically unbiased (ie uniform sampling methods, see below as well)
• successor methods use efficient CAT (ie constant amortized time) or Loopless (ie strictly constant time) algorithms to generate next/prev object from current object (supporting multiple combinatorial orderings along the way, see above) (note a couple of methods are linear time algorithms because the lib does not use extra space to store information between successive runs and also support static random access to successors so any extra is computed at run-time, but can easily be made CAT or even Loopless by storing extra information, eg current index position)
• avoid big-integer arithmetic and computational overhead (except if explicit ranking / unranking is needed and objects are large)
• symbolic polynomials use efficient sparse representation
• number-theoretic/math computations support pluggable arithmetics (thus if used can compute with arbitrary precision arithmetic), algorithms implemented are efficient but not necessarily the most efficient version (theoretically) possible (eg default Euclidean algorithm for gcd used, although optimized), possible to implement even faster algorithms in future verions

Note that Abacus can generate very large, and also randomized, combinatorial objects without ever using biginteger arithmetic due to design and implementation, except if arbitrary random, ranking and unranking have to be used (see above)

Credits and References

See the comments in the code for algorithms and references used.

• The Art of Computer Programming, Donald Knuth
• FXT library, Joerg Arndt and his PhD thesis
• Combinatorial Algorithms, Albert Nijenhuis, Herbert Wilf
• Combinatorial Generation, Frank Ruskey
• Generating Functionology, Herbert Wilf
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects, Herbert Wilf
• Permutation Generation Methods, Robert Sedgewick
• A Versatile Algorithm to Generate Various Combinatorial Structures, Pramod Ganapathi, Rama B
• Generating All and Random Instances of a Combinatorial Object, Ivan Stojmenovic including the section on random generation without large integers & with only one PRNG call
• Efficient Generation of Set Partitions, Michael Orlov
• [Algorithms for Unranking Combinations and Other Related Choice Funct