Skip to content

Latest commit

 

History

History
316 lines (272 loc) · 26.8 KB

README.md

File metadata and controls

316 lines (272 loc) · 26.8 KB
Raw

Abacus

A Combinatorics and Algebraic Number Theory Symbolic Computation library for Javascript, Python

version 1.0.9 in progress (~ 331kB minified)

abacus combinatorial numbers

Abacus.js, Abacus.min.js

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

Abacus uses (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.

Abacus Live

see also:

  • Abacus advanced Combinatorics and Algebraic Number Theory Symbolic Computation library for JavaScript, Python
  • TensorView view array data as multidimensional tensors of various shapes efficiently
  • Geometrize Computational Geometry and Rendering Library for JavaScript
  • Plot.js simple and small library which can plot graphs of functions and various simple charts and can render to Canvas, SVG and plain HTML
  • CanvasLite an html canvas implementation in pure JavaScript
  • Rasterizer stroke and fill lines, rectangles, curves and paths, without canvas
  • Gradient create linear, radial, conic and elliptic gradients and image patterns without canvas
  • css-color simple class to parse and manipulate colors in various formats
  • MOD3 3D Modifier Library in JavaScript
  • HAAR.js image feature detection based on Haar Cascades in JavaScript (Viola-Jones-Lienhart et al Algorithm)
  • HAARPHP image feature detection based on Haar Cascades in PHP (Viola-Jones-Lienhart et al Algorithm)
  • FILTER.js video and image processing and computer vision Library in pure JavaScript (browser and node)
  • Xpresion a simple and flexible eXpression parser engine (with custom functions and variables support), based on GrammarTemplate, for PHP, JavaScript, Python
  • Regex Analyzer/Composer Regular Expression Analyzer and Composer for PHP, JavaScript, Python
  • GrammarTemplate grammar-based templating for PHP, JavaScript, Python
  • codemirror-grammar transform a formal grammar in JSON format into a syntax-highlight parser for CodeMirror editor
  • ace-grammar transform a formal grammar in JSON format into a syntax-highlight parser for ACE editor
  • prism-grammar transform a formal grammar in JSON format into a syntax-highlighter for Prism code highlighter
  • highlightjs-grammar transform a formal grammar in JSON format into a syntax-highlight mode for Highlight.js code highlighter
  • syntaxhighlighter-grammar transform a formal grammar in JSON format to a highlight brush for SyntaxHighlighter code highlighter
  • SortingAlgorithms implementations of Sorting Algorithms in JavaScript
  • PatternMatchingAlgorithms implementations of Pattern Matching Algorithms in JavaScript

Contents

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)

Algebraic Number Theory

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

  • Algebraic Rings / 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 other math utilities can be dynamicaly 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 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 statisticaly 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 optimised), possible to implement even faster algorithms in future verions

Note that the lib can generate very large (and also randomised) 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.

Example API

let o = Abacus.Permutation(4);
console.log(String(o.total()));
console.log('---');
for (let item of o)
{
    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

let o = Abacus.Partition(6);
console.log(String(o.total()));
console.log('---');
for (let item of o)
{
    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

let field = Abacus.Ring.Q("x").associatedField();

let m = 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 language iterator/iterable patterns (e.g ES6 iterator protocol, Python __iter__ interface, ..). Combinatorial objects additionaly support a doubly-linked list-like interface, i.e prev/next accessors [DONE]
  • support biginteger combinatorial computations e.g large factorials [DONE], the lib does not support biginteger arithmetic, but arithmetic routines have been made dynamicaly pluggable and one can use an external implementation to support combinatorics with bigintegers where needed as needed, see test examples for an example
  • support multiple combined custom iterator orderings, i.e lex, colex, reversed, reflected, random seamlessly and uniformly, both forward and backward [DONE, random ordering may be optimised further]
  • support efficient successor methods (preferably CAT/Loopless methods) to generate next/prev object from current object [DONE]
  • support efficient ranking / unranking algorithms and associated methods (preferably of O(n) or O(nlgn) complexity) for supported orderings [DONE]
  • support multiple combinatorial orderings (ie lex, colex, reflex, refcolex, minimal, ..) directly in the successor methods instead of using post-transformations on object [DONE]
  • support unique and uniform random ordering traversals for all combinatorial objects, so that the space of a combinatorial object can be traversed in any 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 .random methods uniformly and unbiasedly sample the combinatorial object space (methods use unbiased sampling algorithms, however results in certain cases might depend on quality of PRNGs) [DONE]
  • support algebraic composition/cascading of combinatorial objects to construct new combinatorial objects (eg all combinations = all permutations OF all unique combinations) [DONE]
  • support generation of supported combinatorial objects with additional user-defined patterns/templates of constraints to satisfy e.g "only combinatorial objects matching '(n)(m)(1){2}(){3}(0)((n+1))((n+m)){4}'" pattern.. [DONE]
  • add LatinSquare, MagicSquare algorithms [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]
  • fix ginv (Moore-Penrose Inverse) computation [DONE]
  • implement (faster) numeric EVD/SVD computation (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)
  • implement Aberth polynomial root finding algorithm (TODO)
  • implement LLL algorithm (TODO)
  • implement groebner basis computations (Buchberger algorithm) [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 (eg fibonacci, factorial, gcd, ..) [DONE PARTIALY]
  • full support for colex ordering Composition & Partition [DONE PARTIALY]
  • add efficient rank/unrank methods for Composition & Partition [DONE]
  • add efficient rank/unrank methods for DerangementPermutation [DONE]
  • add efficient rank/unrank methods for ConnectedPermutation [DONE]
  • add efficient rank/unrank methods for InvolutionPermutation [DONE] (not very efficient)
  • support minimal/gray ordering (and successor) for all supported combinatorial objects (TODO)
  • support generation (and counting) of combinatorial objects (including the basic supported ones) based on generic user-defined symbolic constraints / symmetries / rules to satisfy, for example permutations defined symbolicaly and directly by their symmetries / constraints instead of being hardcoded as elementary objects (TODO?, see using filtering as a similar alternative to this approach)
  • support graph-based combinatorial objects like Graph, Grammar,.. (TODO?) (for regular grammars and expressions see RegexAnalyzer for an example)