[HN Gopher] Permutation Generation Methods [pdf]
       ___________________________________________________________________
        
       Permutation Generation Methods [pdf]
        
       Author : qsort
       Score  : 52 points
       Date   : 2022-08-23 14:49 UTC (8 hours ago)
        
 (HTM) web link (homepage.divms.uiowa.edu)
 (TXT) w3m dump (homepage.divms.uiowa.edu)
        
       | ur-whale wrote:
       | Article is a scan so can't be searched.
       | 
       | Any mention of symmetric crypto in there?
       | 
       | After all, permutation generation is what a sizable chunk
       | symmetric crypto is about.
       | 
       | [edit]: and now that I've skimmed through the paper, I see it is
       | not really about permutation generation but rather permutation
       | enumeration, so symmetric crypto is out.
        
       | lkuty wrote:
       | Reminds of the french article by Laisant published in 1888 about
       | the factorial number system (factoradic) and its application to
       | permutations. http://www.numdam.org/item/?id=BSMF_1888__16__176_0
       | 
       | I also found an article by James McCaffrey named "Using
       | Permutations in .NET for Improved Systems Security" but I can't
       | find it again.
       | 
       | I used them a few years ago to enumarate all possible
       | permutations to find the best solution to a small sample of TSP
       | and compare it to the approximate solution found by an algorithm.
       | 
       | EDIT: looks like my source was just
       | https://en.wikipedia.org/wiki/Factorial_number_system
        
         | qsort wrote:
         | Interestingly, this is basically what CPython does to implement
         | its native permutations function. The C source is, as always,
         | extremely easy to understand:
         | https://github.com/python/cpython/blob/main/Modules/itertool...
        
           | 082349872349872 wrote:
           | nice find in Numdam; chouette !
           | 
           | IIRC Iverson presents the isomorphism between factoradic
           | ([R]adix) and indexed ([D]irect) permutation representations
           | in his Turing Award Lecture[0] (p456, via a pair of APL
           | functions):                   DFR:o[1],X+o[1]<=X-DFR
           | 1|o:O=po:o         RFD:o[1],RFD X-o[1]<=X-1|o:O=po:o
           | 
           | [0] https://dl.acm.org/ft_gateway.cfm?id=1283935&type=pdf
        
       | bArray wrote:
       | A related interesting problem is superpermutations [1]. This is
       | the same problem that an anonymous 4chan poster helped bring some
       | light to lower bounds on shortest superpatterns [2]. The Google
       | group is worth a shout for their efforts [3].
       | 
       | Surprisingly, we only have optimal superpermutations for really
       | low values on N [4].
       | 
       | I tried my hand at auto-generating symmetric patterns (which turn
       | out to not be optimal after some value of N (6?)), but the
       | problem is quite tough. Currently the best approaches appear to
       | be achieved by using a TSP solver.
       | 
       | [1]
       | https://www.gregegan.net/SCIENCE/Superpermutations/Superperm...
       | 
       | [2] https://oeis.org/A180632/a180632.pdf
       | 
       | [3] https://groups.google.com/g/superpermutators
       | 
       | [4]
       | https://github.com/superpermutators/superperm/tree/master/su...
        
         | WorkerBee28474 wrote:
         | Wow, I never thought I would ever see "Anonymous 4chan Poster"
         | credited as the co-author of a paper.
         | 
         | I guess it makes sense as an implication of the idea that "On
         | the Internet, nobody knows you're a dog." [0]
         | 
         | [0] http://www.paulgraham.com/hiring.html
        
       | llimllib wrote:
       | I only looked very briefly, but Knuth's fascicle 2b covers
       | similar material. You can read a draft version here: https://www-
       | cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz (or purchase the real
       | one, obviously)
       | 
       | I was surprised when I went to implement some of them a decade
       | ago that it's actually very readable, if Knuth's reputation
       | scares you.
       | 
       | I made visualizations of a few of them way back then:
       | https://billmill.org/permvis.html
        
       | nayuki wrote:
       | My preferred method:                   int[] array = {0, 1, 2, 3,
       | 4, 5, 6, 7, 8, 9};         do {             print(array);
       | } while (nextPermutation(array));
       | 
       | https://www.nayuki.io/page/next-lexicographical-permutation-...
       | 
       | This even works with duplicate values.
        
         | fjfaase wrote:
         | For a C++ implementation see the iterator class Permutations in
         | https://iwriteiam.nl/FSwNcolour_cpp.txt
        
       ___________________________________________________________________
       (page generated 2022-08-23 23:01 UTC)