Permutation Iteration and Random Access

• cl-permutation

  4 47 3.5 Common Lisp

  Permutations and permutation groups in Common Lisp.

Here is Lisp code [1] that maps all sorts of combinatorial objects—permutations, bit sets, base-B integers, multi-set permutations, etc.—perfectly into the smallest set of integers [0, n-1] and back. (In a sense, it's a perfect hash.) This is used to efficiently solve combinatorial puzzles.

[1] https://github.com/stylewarning/cl-permutation/blob/master/s...

• ChessPositionRanking

  29 132 2.5 Haskell

  Software suite for ranking chess positions and accurately estimating the number of legal chess positions

Multinomial rankings can be combined with a dozen others to rank a subset of all chess positions including all legal ones. This allows one to sample millions of random such positions, determine how many are legal, and thus obtain an accurate estimate of 4.8&10^44 legal chess positions [2].

[1] https://github.com/tromp/ChessPositionRanking/blob/main/src/...

[2] https://github.com/tromp/ChessPositionRanking

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

• opus

  26 2,103 9.6 C

  Modern audio compression for the internet.

  

There is a pattern here (that also goes with the author's prior article on inverting gauss' sum formula): Generally if if you can make a formula that counts the combination of things you can convert that into a code to encode and decode those combinations into indexes.

So for example the opus audio codec needs to encode/decode vectors of dimension n whos absolute values sum to k. https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74

Or this rolling cuckoo filter that optimally encode/decode four sorted numbers in a range 0..2N with the constraint that the they span a range of N. https://github.com/sipa/bitcoin/blob/202006_cuckoo_filter/sr...

If you're lucky there will be closed form expressions for the encoding and decoding equations. (There for both of the above, at least for some parameters, but in both those examples the implementations use small tables because for the ranges involved the tables end up being faster than sqrts).

• bitcoin

  28 86 0.0 TypeScript

  Bitcoin integration/staging tree (by sipa)

There is a pattern here (that also goes with the author's prior article on inverting gauss' sum formula): Generally if if you can make a formula that counts the combination of things you can convert that into a code to encode and decode those combinations into indexes.

So for example the opus audio codec needs to encode/decode vectors of dimension n whos absolute values sum to k. https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74

Or this rolling cuckoo filter that optimally encode/decode four sorted numbers in a range 0..2N with the constraint that the they span a range of N. https://github.com/sipa/bitcoin/blob/202006_cuckoo_filter/sr...

If you're lucky there will be closed form expressions for the encoding and decoding equations. (There for both of the above, at least for some parameters, but in both those examples the implementations use small tables because for the ranges involved the tables end up being faster than sqrts).

Suggest a related project