4 ms·

Permutation iteration and random access

55 points by ingve 3y ago

pipo234 3y ago
Nice demonstration, though the C++ is a bit cheesy. (C-style cast, integer signedness, modernize beyond C++98, ... :-)
- Atrix256 3y ago
  Game development tends to make code more in this style, half way between C and C++. The reasoning of this is primarily the need to avoid hidden costs in the STL, but to be honest is also just momentum & culture :)
nullc 3y ago
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. It's often easiest to convert the counting expression into enumeration code if you can express it in a recursive form. So for example the opus audio codec needs to encode/decode signed integer vectors of dimension n whose absolute values sum to k. https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74 https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74 (More writeup on enumerations for that set of combinations here: https://web.archive.org/web/20150619082342/https://people.xiph.org/~tterribe/notes/cwrs.html https://web.archive.org/web/20150619082342/https://people.xi... and https://nt4tn.net/papers/cwrs.pdf https://nt4tn.net/papers/cwrs.pdf) 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/src/cuckoofilter.cpp#L39 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 are 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). Another simple example of these is converting subsets of N out of a collection of M elements, where the underlying counting function is just the binomial function. I often do this when constructing tests for trying many combinations of choices without a whole bunch of nested loops or uglier constructs. Though if you don't need indexing iterating can of often be more simply done in other ways. For a particularly extreme example, to iterate the subsets define your membership as the bits in an unsigned integer. Start with N least significant bits set then update your state each step like so (stopping when the N most significant bits are set): t=(state&-state)+state; state=t|((1<<(popcount(state^t)-2))-1);
reikonomusha 3y ago
Here is Lisp code [1] that maps all sorts of combinatorial objects—permutations, combinations, radix-R integers, multi-set arrangements, etc.—perfectly into the smallest set of integers [0, n-1] and back. (In a sense, they are perfect hash functions.) This is used to help efficiently solve combinatorial puzzles. [1] https://github.com/stylewarning/cl-permutation/blob/master/src/combinatorial-ranking.lisp https://github.com/stylewarning/cl-permutation/blob/master/s...
- 082349872349872 3y ago
  see also http://www.sudleyplace.com/APL/A%20Combinatorial%20Operator%20in%20APL.pdf http://www.sudleyplace.com/APL/A%20Combinatorial%20Operator%... > The goal of this document is to describe a single APL primitive to both count and generate various Combinatorial Arrays: permutations, combinations, compositions, partitions, etc. The unifying (and very APL-like) principle for such a primitive is Gian-Carlo Rota's Twelvefold Way as described in Richard Stanley's "Enumerative Combinatorics", Knuth’s TAoCP, Vol. 4A, and Wikipedia among other references.
legerdemain 3y ago
Given a permutation of a collection of elements, it's trivially possible to find the next permutation (in lexicographic order) without ranking and unranking. Sedgewick 77 [1] calls it the Fischer-Krause algorithm. The traditional (and still readable) reference for generating combinatorial objects such as permutations is Nijenhuis & Wilf's Combinatorial Algorithms. The author of the article ubiquitously misspells "lexicographic" as "lexographic." That might make it harder to Google the term. [1] https://www.princeton.edu/~rblee/ELE572Papers/p137-sedgewick.pdf https://www.princeton.edu/~rblee/ELE572Papers/p137-sedgewick...
tromp 3y ago
The permutation ranking algorithm described in the article can be generalized to a so-called multinomial ranking, one of several rankings implemented in Haskell [1]. E.g. > let r = multinomialRanking (zip "abc" [1..3]) > size r 60 > unrank r 42 "cbcabc" > rank r "cbcabc" 42 Various types of rankings, together with combinators to build up more complex ones, were implemented as part of the chess position ranking project [2] which aims to rank a subset of all chess positions that includes all legal ones: > let cpr = sideToMoveRanking `composeURI` (caseRanking `composeRI` wArmyStatRanking `composeURI` bArmyStatRanking `composeRI` guardRanking `composeRI` enPassantRanking `composeURI` epOppRanking `composeURI` sandwichRanking `composeRI` opposeRanking `composeURI` pawnRanking `composeURI` castleRanking `composeURI` wArmyRanking `composeURI` bArmyRanking `composeURI` pieceRanking) $ emptyURPosition > size cpr 8726713169886222032347729969256422370854716254 > writeFEN . toPosition . unrank cpr $ 2389124290426577024216048831051262280148947032 "1r6/1qrRPk2/1rn1Rn1n/1RQRR2R/3P4/3b2BN/1Knn1b1b/1BR5 w - - 0 1" > rank cpr . fromPosition . readFEN $ "1r6/1qrRPk2/1rn1Rn1n/1RQRR2R/3P4/3b2BN/1Knn1b1b/1BR5 w - - 0 1" 2389124290426577024216048831051262280148947032 Position data includes side to move, castling status, and en-passant status. This ranking 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. [1] https://github.com/tromp/ChessPositionRanking/blob/main/src/Data/Ranking.hs https://github.com/tromp/ChessPositionRanking/blob/main/src/... [2] https://github.com/tromp/ChessPositionRanking https://github.com/tromp/ChessPositionRanking
bobmaxup 3y ago
> Lexographic I also have made this spelling (speech?) error
- wnoise 3y ago
  In addition to lexicographic, lexigraphic is a word, which would sound quite similar in most dialects.
- Atrix256 3y ago
  Fixed, woops.
qsort 3y ago
You can do that by hand writing the number in factorial base: https://en.wikipedia.org/wiki/Factorial_number_system https://en.wikipedia.org/wiki/Factorial_number_system

55 points by ingve 3y ago

pipo234 3y ago

Nice demonstration, though the C++ is a bit cheesy. (C-style cast, integer signedness, modernize beyond C++98, ... :-)

Atrix256 3y ago
Game development tends to make code more in this style, half way between C and C++. The reasoning of this is primarily the need to avoid hidden costs in the STL, but to be honest is also just momentum & culture :)

nullc 3y ago

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. It's often easiest to convert the counting expression into enumeration code if you can express it in a recursive form. So for example the opus audio codec needs to encode/decode signed integer vectors of dimension n whose absolute values sum to k. https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74 https://github.com/xiph/opus/blob/master/celt/cwrs.c#L74 (More writeup on enumerations for that set of combinations here: https://web.archive.org/web/20150619082342/https://people.xiph.org/~tterribe/notes/cwrs.html https://web.archive.org/web/20150619082342/https://people.xi... and https://nt4tn.net/papers/cwrs.pdf https://nt4tn.net/papers/cwrs.pdf) 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/src/cuckoofilter.cpp#L39 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 are 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). Another simple example of these is converting subsets of N out of a collection of M elements, where the underlying counting function is just the binomial function. I often do this when constructing tests for trying many combinations of choices without a whole bunch of nested loops or uglier constructs. Though if you don't need indexing iterating can of often be more simply done in other ways. For a particularly extreme example, to iterate the subsets define your membership as the bits in an unsigned integer. Start with N least significant bits set then update your state each step like so (stopping when the N most significant bits are set): t=(state&-state)+state; state=t|((1<<(popcount(state^t)-2))-1);

reikonomusha 3y ago

Here is Lisp code [1] that maps all sorts of combinatorial objects—permutations, combinations, radix-R integers, multi-set arrangements, etc.—perfectly into the smallest set of integers [0, n-1] and back. (In a sense, they are perfect hash functions.) This is used to help efficiently solve combinatorial puzzles. [1] https://github.com/stylewarning/cl-permutation/blob/master/src/combinatorial-ranking.lisp https://github.com/stylewarning/cl-permutation/blob/master/s...

082349872349872 3y ago
see also http://www.sudleyplace.com/APL/A%20Combinatorial%20Operator%20in%20APL.pdf http://www.sudleyplace.com/APL/A%20Combinatorial%20Operator%... > The goal of this document is to describe a single APL primitive to both count and generate various Combinatorial Arrays: permutations, combinations, compositions, partitions, etc. The unifying (and very APL-like) principle for such a primitive is Gian-Carlo Rota's Twelvefold Way as described in Richard Stanley's "Enumerative Combinatorics", Knuth’s TAoCP, Vol. 4A, and Wikipedia among other references.

legerdemain 3y ago

Given a permutation of a collection of elements, it's trivially possible to find the next permutation (in lexicographic order) without ranking and unranking. Sedgewick 77 [1] calls it the Fischer-Krause algorithm. The traditional (and still readable) reference for generating combinatorial objects such as permutations is Nijenhuis & Wilf's Combinatorial Algorithms. The author of the article ubiquitously misspells "lexicographic" as "lexographic." That might make it harder to Google the term. [1] https://www.princeton.edu/~rblee/ELE572Papers/p137-sedgewick.pdf https://www.princeton.edu/~rblee/ELE572Papers/p137-sedgewick...

tromp 3y ago

The permutation ranking algorithm described in the article can be generalized to a so-called multinomial ranking, one of several rankings implemented in Haskell [1]. E.g. > let r = multinomialRanking (zip "abc" [1..3]) > size r 60 > unrank r 42 "cbcabc" > rank r "cbcabc" 42 Various types of rankings, together with combinators to build up more complex ones, were implemented as part of the chess position ranking project [2] which aims to rank a subset of all chess positions that includes all legal ones: > let cpr = sideToMoveRanking `composeURI` (caseRanking `composeRI` wArmyStatRanking `composeURI` bArmyStatRanking `composeRI` guardRanking `composeRI` enPassantRanking `composeURI` epOppRanking `composeURI` sandwichRanking `composeRI` opposeRanking `composeURI` pawnRanking `composeURI` castleRanking `composeURI` wArmyRanking `composeURI` bArmyRanking `composeURI` pieceRanking) $ emptyURPosition > size cpr 8726713169886222032347729969256422370854716254 > writeFEN . toPosition . unrank cpr $ 2389124290426577024216048831051262280148947032 "1r6/1qrRPk2/1rn1Rn1n/1RQRR2R/3P4/3b2BN/1Knn1b1b/1BR5 w - - 0 1" > rank cpr . fromPosition . readFEN $ "1r6/1qrRPk2/1rn1Rn1n/1RQRR2R/3P4/3b2BN/1Knn1b1b/1BR5 w - - 0 1" 2389124290426577024216048831051262280148947032 Position data includes side to move, castling status, and en-passant status. This ranking 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. [1] https://github.com/tromp/ChessPositionRanking/blob/main/src/Data/Ranking.hs https://github.com/tromp/ChessPositionRanking/blob/main/src/... [2] https://github.com/tromp/ChessPositionRanking https://github.com/tromp/ChessPositionRanking

bobmaxup 3y ago

> Lexographic I also have made this spelling (speech?) error

wnoise 3y ago
In addition to lexicographic, lexigraphic is a word, which would sound quite similar in most dialects.
Atrix256 3y ago
Fixed, woops.

qsort 3y ago

You can do that by hand writing the number in factorial base: https://en.wikipedia.org/wiki/Factorial_number_system https://en.wikipedia.org/wiki/Factorial_number_system