Combinatorial Algorithms

What Hacker News says

1. legerdemainAug 2023
   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...

   Show morethread
2. mjcohenMay 2020
   Of course this is a n^2 sort. Combinatorial Algorithms by Nijenhuis and Wilf, 1975, has a 23 lines Fortran implementation of Heapsort, a n log n sort. It is available on the web and easily found, so I am going to list it here. I am not going to attempt to convert it to C.

   Note: Enjoy discriminating between the one and the lower-case l.

         subroutine hpsort(n,b)
         integer b(500),bstar
         n1=n
         l=1+n/2
      11 l=l-1
         bstar=b(l)
         goto 30
      25 bstar=b(n1)
         b(n1)=b(1)
      29 n1=n1-1
      30 l1=l
      31 m=2*l1
         if(m-n1)32,33,37
      32 if(b(m+1).ge.b(m)) m=m+1
      33 if(bstar.ge.b(m))goto 37
         b(l1)=b(m)
         l1=m
         goto 31
      37 b(l1)=bstar
         if(l.gt.1)goto 11
         if(n1.ge.2)goto 25
         return
         end

   Show morethread