Abacus

ACombinatoricsandAlgebraic Number TheorySymbolic Computation library for Javascript, Python

version 1.0.9 in progress(~ 331kB minified)

Abacus.js,Abacus.min.js

Abacusis a flexible library containing methods and associated math utilities for (fast) combinatorial object computation and integer / number theoretic computation. It builds on (and extends) adeprecated previous project for PHP, Simulacra.

Abacususes (for the most part) self-contained and standalone methods, so they can be easily copy-pasted in other projects, in case only a few methods are needed and not the whole library.

see also:

• Abacusadvanced Combinatorics and Algebraic Number Theory Symbolic Computation library for JavaScript, Python
• TensorViewview array data as multidimensional tensors of various shapes efficiently
• GeometrizeComputational Geometry and Rendering Library for JavaScript
• Plot.jssimple and small library which can plot graphs of functions and various simple charts and can render to Canvas, SVG and plain HTML
• CanvasLitean html canvas implementation in pure JavaScript
• Rasterizerstroke and fill lines, rectangles, curves and paths, without canvas
• Gradientcreate linear, radial, conic and elliptic gradients and image patterns without canvas
• css-colorsimple class to parse and manipulate colors in various formats
• MOD33D Modifier Library in JavaScript
• HAAR.jsimage feature detection based on Haar Cascades in JavaScript (Viola-Jones-Lienhart et al Algorithm)
• HAARPHPimage feature detection based on Haar Cascades in PHP (Viola-Jones-Lienhart et al Algorithm)
• FILTER.jsvideo and image processing and computer vision Library in pure JavaScript (browser and node)
• Xpresiona simple and flexible eXpression parser engine (with custom functions and variables support), based onGrammarTemplate,for PHP, JavaScript, Python
• Regex Analyzer/ComposerRegular Expression Analyzer and Composer for PHP, JavaScript, Python
• GrammarTemplategrammar-based templating for PHP, JavaScript, Python
• codemirror-grammartransform a formal grammar in JSON format into a syntax-highlight parser for CodeMirror editor
• ace-grammartransform a formal grammar in JSON format into a syntax-highlight parser for ACE editor
• prism-grammartransform a formal grammar in JSON format into a syntax-highlighter for Prism code highlighter
• highlightjs-grammartransform a formal grammar in JSON format into a syntax-highlight mode for Highlight.js code highlighter
• syntaxhighlighter-grammartransform a formal grammar in JSON format to a highlight brush for SyntaxHighlighter code highlighter
• SortingAlgorithmsimplementations of Sorting Algorithms in JavaScript
• PatternMatchingAlgorithmsimplementations of Pattern Matching Algorithms in JavaScript

Contents

• Live Playground Example
• Features
• Combinatorial and Number Theory Examples
• 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 compositionandsequencesof combinatorial objects to construct new combinatorial objects (egall combinations=all permutationsOFall unique combinations,seetest/permutations_of_combinations.jsandtest/permutations_of_permutations.js,k-Derangements=(n,k) Combinationscombined With(n-k) Derangements,seetest/k-derangements.jsorall subsets=(n,0)Combinations + (n,1)Combinations +.. + (n,n-1)Combinations + (n,n)Combinations,seetest/combination_subsets.js)

• custom and built-infilterswhich can select and generate any custom and complex combinatorial object from filtering other combinatorial objects as efficiently as possible (e.g seetest/filtered.js,test/filtered_partitions.js). Alsoalgebraic / boolean composition of filters(i.e.NOT(),.AND(),.OR()and so on..).Notethat filtering should beused with caution and only if no other method is currently possibleto generate the desired combinatorial object asfiltering is equivalent to exhaustive searchover the space of the original combinatorial object and as such can be an inefficient way to generate a combinatorial object (e.g seetest/filtered.js).Note2with filtering applied some methods like.total(),.hasNext()still return data of the original objectnotthe 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 rangeof combinatorial objects in a number of supported orderings (ielex,colex,random,..) (and with filtering applied, if set).Noteunrankmethods have to be implemented for this feature to work

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

Algebraic Number Theory

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

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

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

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

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

• AlgebraicRings /Fields eg.Ring.Z(), Ring.Q(), Ring.C(), Ring.Q( "x", "y" ),..(test/polynomials.js,test/multivariate.js,test/ratfuncs.js)

• Matrix(test/matrices.js)with coefficients from a Ring (default: Integer Ring.Z())

• 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)

• big-integer arithmetic,PRNGs and othermathutilities can bedynamicaly pluggable using external implementations,making the lib very flexible especialy with respect to handling big-integers & (pseudo-)random number generators (eg examples and tests use the excellentBigInteger.js)

Performance

• first/last,random,rank/unrankmethods useefficient linearO(n)(orlog-linearO(nlgn))time and spacealgorithms (notea couple of rank/unrank methods are ofO(n^2)or higher order)
• randommethods arestatisticaly unbiased(ie uniform sampling methods, see below as well)
• successormethods useefficient 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) (notea couple of methods arelinear timealgorithms 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 atrun-time,but can easily be madeCATor evenLooplessby storing extra information, eg current index position)
• avoid big-integer arithmetic and computational overhead(except if explicitranking/unrankingis 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 forgcdused, although optimised), possible to implement even faster algorithms in future verions

Notethat the lib can generatevery large(and alsorandomised) combinatorial objectswithout ever usingbiginteger arithmetic due to design and implementation except if arbitraryrandom,rankingandunrankinghave 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 Arndtand hisPhD 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 Stojmenovicincluding the section on random generationwithout large integers&with only onePRNGcall
• Efficient Generation of Set Partitions, Michael Orlov
• Algorithms for Unranking Combinations and Other Related Choice Functions, Zbigniew Kokosinski
• Analytic Combinatorics, Philippe Flajolet, Robert Sedgewickcan also be used to produce combinatorial generation algorithms instead of just generating functions for counting and statistics
• Gray Code, wikipedia
• A Survey of Combinatorial Gray Codes, Carla Savage
• Generalized Gray Codes with Applications, DAH-JYH GUAN
• A SIMPLE SEQUENCING AND RANKING METHOD THAT WORKS ON ALMOST ALL GRAY CODES, Timothy R. Walsh
• Gray Code Enumeration of Families of Integer Partitions, David Rasmussen, Carla D. Savage, Douglas B. West
• A GRAY CODE FOR SET PARTITIONS, Richard KAYE
• Combinatorial Generation by Fusing Loopless Algorithms, Tadao Takaoka, Stephen Violich
• Make good (Pseudo-)Random Number Generators
• Handbook of Applied Cryptography, Chapter 4
• The Quadratic Sieve Factoring Algorithm, Eric Landquist
• A Beginner’s Guide To The General Number Field Sieve, Michael Case
• Implementation of a New Primality Test, H. Cohen, A.K. Lenstra
• Integer Algorithms to solve Diophantine Linear Equations and Systems, Florentin Smarandache
• Linear Diophantine Equations, William J. Gilbert, Anu Pathria
• Chinese Remainder Theorem, wikipedia
• A multivariable Chinese remainder theorem, Oliver Knill
• Solving a System of Linear Diophantine Equations with Lower and Upper Bounds on the Variables, K. Aardal, C.A.J. Hurkens, A.K. Lenstra
• Integer Programming with a Fixed Number of Variables, H.W. Lenstra
• Integer Programming with 2-Variable Equations and 1-Variable Inequalities, Bodirsky, Nordh, Von Oertzen
• Fourier-Motzkin Elimination, wikipedia
• Fourier's Elimination: Which to Choose?, Jean-Louis Imbert
• Complexity Estimates for Fourier-Motzkin Elimination, Rui-Juan Jing, Marc Moreno-Maza, Delaram Talaashrafi
• Fourier-Motzkin Elimination Extension to Integer Programming Problems, H.P. Williams
• Affine Monoids, Hilbert Bases and Hilbert Functions, Robert Koch (PhD thesis)
• Numerical algorithms for the computation of the Smith normal form of integral matrices, C. Koukouvinos, M. Mitrouli, J. Seberry
• Computational solutions of matrix problems over an integral domain, Erwin H. Bareiss
• Fraction-free matrix factors: new forms for LU and QR factors, Wenqin ZHOU, David J. JEFFREY
• Fraction-Free Methods for Determinants, Deanna Richelle Leggett (MSc thesis)
• Moore-Penrose Generalised Inverse, wikipedia
• The Moore-Penrose Pseudoinverse. A Tutorial Review of the Theory, J.C.A. Barata, M.S. Hussein
• A general matrix eigenvalue algorithm, Charles F. Van Loan
• Algorithms and Data Structures for Sparse Polynomial Arithmetic, M. Asadi, A. Brandt, R. H. C. Moir, M. M. Maza
• High Performance Sparse Multivariate Polynomials: Fundamental Data Structures and Algorithms, Alex Brandt (MSc thesis)
• GCDHEU: Heuristic Polynomial GCD Algorithm Based On Integer GCD Computation, B. W. Char, K. O. Geddes and G. H. Gonnet
• An improved EZ-GCD algorithm for multivariate polynomials, Kuniaki Tsuji
• The EEZ-GCD algorithm, Paul S. Wang
• Three new algorithms for multivariate polynomial GCD, T. Sasaki and M. Suzuki
• Greedy Algorithms for Optimizing Multivariate Horner Schemes, M. Ceberio and V. Kreinovich
• Gröbner basis, wikipedia
• Buchberger's algorithm, wikipedia
• Faugère's F4 and F5 algorithms, wikipedia
• A Note on Multivariate Polynomial Division and Gröbner Bases, A. T. Lipkovski and S. Zeada
• Roots of multivariate polynomials, Chapter 11
• Algorithms for Normal Forms for Matrices of Polynomials and Ore Polynomials, Howard Cheng (PhD thesis)
• Fast Methods for Large Scale Singular Value Decomposition, Nela Bosner (PhD thesis)
• Square-free Decomposition, wikipedia
• Partial Fraction Decomposition, wikipedia
• Geometrical properties of polynomial roots, wikipedia
• Newton's method, wikipedia
• Aberth method, wikipedia
• Numerical computation of polynomial zeros by means of Aberth's method, D. A. Bini
• General Complex Polynomial Root Solver and Its Further Optimization for Binary Microlenses, Jan Skowron and Andrew Gould

Example API

leto=Abacus.Permutation(4);
console.log(String(o.total()));
console.log('---');
for(letitemofo)
{
console.log(item.join(','));
}

24
---
0,1,2,3
0,1,3,2
0,2,1,3
0,2,3,1
0,3,1,2
0,3,2,1
1,0,2,3
1,0,3,2
1,2,0,3
1,2,3,0
1,3,0,2
1,3,2,0
2,0,1,3
2,0,3,1
2,1,0,3
2,1,3,0
2,3,0,1
2,3,1,0
3,0,1,2
3,0,2,1
3,1,0,2
3,1,2,0
3,2,0,1
3,2,1,0

leto=Abacus.Partition(6);
console.log(String(o.total()));
console.log('---');
for(letitemofo)
{
console.log(item.join('+'));
}

11
---
1+1+1+1+1+1
2+1+1+1+1
2+2+1+1
2+2+2
3+1+1+1
3+2+1
3+3
4+1+1
4+2
5+1
6

letfield=Abacus.Ring.Q("x").associatedField();

letm=Abacus.Matrix(field,[
[field.fromString("x-1"),field.fromString("x^2-1")],
[field.fromString("x^2-1"),field.fromString("x-1")]
]);

console.log(m.toString());
console.log(m.inv().toString());
console.log(m.inv().mul(m).toString());

| x-1 x^2-1|
|x^2-1 x-1|

| -1/(x^3+x^2-2*x) (x+1)/(x^3+x^2-2*x)|
|(x+1)/(x^3+x^2-2*x) -1/(x^3+x^2-2*x)|

|1 0|
|0 1|

Todo

• apply built-in languageiterator/iterablepatterns (e.g ES6iteratorprotocol, Python__iter__interface,..). Combinatorial objects additionaly support adoubly-linked list-like interface, i.eprev/nextaccessors[DONE]
• supportbigintegercombinatorial computations e.g large factorials[DONE],the libdoes not supportbiginteger arithmetic, but arithmetic routines have been madedynamicaly pluggableand one can use an external implementation to support combinatorics with bigintegers where needed as needed, see test examples for an example
• supportmultiple combined custom iterator orderings,i.elex,colex,reversed,reflected,randomseamlessly and uniformly, both forward and backward[DONE,randomordering may be optimised further]
• supportefficient successor methods(preferablyCAT/Looplessmethods) to generate next/prev object from current object[DONE]
• supportefficient ranking / unranking algorithmsand associated methods (preferably ofO(n)orO(nlgn)complexity) for supported orderings[DONE]
• support multiple combinatorial orderings (ielex,colex,reflex,refcolex,minimal,..)directly in the successor methodsinstead of using post-transformations on object[DONE]
• supportunique and uniform random ordering traversalsfor all combinatorial objects, so that the space of a combinatorial object can be traversed inany random ordering uniquely and unbiasedly(useful in some applications, eg backtracking)[DONE, see reference, used as custom iterator ordering, see above, may be optimised further]
• make sure the.randommethodsuniformly and unbiasedly sample the combinatorial object space(methods use unbiased sampling algorithms, however results in certain cases might depend onquality of PRNGs)[DONE]
• support algebraic composition/cascading of combinatorial objects to construct new combinatorial objects (egall combinations=all permutationsOFall unique combinations)[DONE]
• support generation of supported combinatorial objects with additionaluser-defined patterns/templates of constraintsto satisfy e.g"only combinatorial objects matching'(n)(m)(1){2}(){3}(0)((n+1))((n+m)){4}'"pattern..[DONE]
• addLatinSquare,MagicSquarealgorithms[DONE]
• add run-time/lazy custom and/or built-in filtering support (with support for filter composition as well) to generate and select custom and complex combinatorial objects from filtering other combinatorial objects as efficiently as possible[DONE]
• support efficient primality tests and prime sieves[DONE]
• support efficient integer factorization algorithms[DONE PARTIALY]
• support solutions of (systems of)linear diophantine and linear congruence equations(with one or many variables)[DONE]
• add Rank Factorisation[DONE]
• fixginv(Moore-Penrose Inverse) computation[DONE]
• implement (faster) numericEVD/SVDcomputation (TODO)
• support general and least-squares solutions of arbitrary linear systems[DONE]
• use sparse representation for polynomials (univariate and multivariate) instead of the, in general, inefficient dense representation (and optimise associated arithmetic operations)[DONE]
• support (univariate) polynomial (partial) factorisation, (rational) root finding[DONE]
• support multivariate polynomial, multivariate operations[DONE]
• support multivariate polynomial GCD, (approximate) root finding (TODO)
• implementAberthpolynomial root finding algorithm (TODO)
• implementLLLalgorithm (TODO)
• implement groebner basis computations (Buchbergeralgorithm)[DONE]
• support generic algebraic Rings and Fields (including rings of polynomials and fraction fields of polynomials)[DONE]
• use faster number-theoretic/integer algorithms (maybe fine-tuned further based on if BigInteger Arithmetic is used) if worth the trouble (egfibonacci,factorial,gcd,..)[DONE PARTIALY]
• full support forcolexorderingComposition&Partition[DONE PARTIALY]
• add efficientrank/unrankmethods forComposition&Partition[DONE]
• add efficientrank/unrankmethods forDerangementPermutation[DONE]
• add efficientrank/unrankmethods forConnectedPermutation[DONE]
• add efficientrank/unrankmethods forInvolutionPermutation[DONE] (not very efficient)
• supportminimal/grayordering (and successor) for all supported combinatorial objects (TODO)
• support generation (and counting) of combinatorial objects (including the basic supported ones) based ongeneric user-defined symbolic constraints / symmetries / rulesto satisfy, for examplepermutationsdefined symbolicaly and directly by theirsymmetries / constraintsinstead of being hardcoded as elementary objects (TODO?, see usingfilteringas a similar alternative to this approach)
• supportgraph-basedcombinatorial objects likeGraph,Grammar,.. (TODO?) (for regular grammars and expressions seeRegexAnalyzerfor an example)