[HN Gopher] Permutation iteration and random access
       ___________________________________________________________________
        
       Permutation iteration and random access
        
       Author : ingve
       Score  : 51 points
       Date   : 2023-08-23 06:23 UTC (16 hours ago)
        
 (HTM) web link (blog.demofox.org)
 (TXT) w3m dump (blog.demofox.org)
        
       | qsort wrote:
       | You can do that by hand writing the number in factorial base:
       | https://en.wikipedia.org/wiki/Factorial_number_system
        
       | tromp wrote:
       | 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/...
       | 
       | [2] https://github.com/tromp/ChessPositionRanking
        
       | reikonomusha wrote:
       | 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/s...
        
         | 082349872349872 wrote:
         | see also
         | 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._
        
       | bobmaxup wrote:
       | > Lexographic
       | 
       | I also have made this spelling (speech?) error
        
         | Atrix256 wrote:
         | Fixed, woops.
        
         | wnoise wrote:
         | In addition to lexicographic, lexigraphic is a word, which
         | would sound quite similar in most dialects.
        
       | legerdemain wrote:
       | 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...
        
       | pipo234 wrote:
       | Nice demonstration, though the C++ is a bit cheesy. (C-style
       | cast, integer signedness, modernize beyond C++98, ... :-)
        
         | Atrix256 wrote:
         | 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 :)
        
       ___________________________________________________________________
       (page generated 2023-08-23 23:02 UTC)