guile-project-euler-solutions/024/solution.scm

;; https://projecteuler.net/problem=24

;; Lexicographic permutations

;; Problem 24

;; A permutation is an ordered arrangement of objects. For
;; example, 3124 is one possible permutation of the digits
;; 1, 2, 3 and 4. If all of the permutations are listed
;; numerically or alphabetically, we call it lexicographic
;; order. The lexicographic permutations of 0, 1 and 2 are:

;; 012   021   102   120   201   210

;; What is the millionth lexicographic permutation of the
;; digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?


(import
 (except (rnrs base) let-values map)
 (only (guile)
       lambda* λ)
 (ice-9 match)
 (srfi srfi-1)  ; list stuff
 (contract)
 (prefix (lib math) math:)
 (lib list-helpers))


;; 0123456789 + 9   (9*1)
;; 0123456798 + 81  (9*9)
;; 0123456879 + 18  (9*2)
;; 0123456897 + 81  (9*9)
;; 0123456978 + 9   (9*1)
;; 0123456987 + 702 (9*9*9 - 9*3 = 9*78)
;; 0123457689 ...

;; There seems to be some pattern there, but not sure what
;; it is exactly.

;; I guess one has to really implement permutating a list so
;; that the permutations are in order.

;; idea: stream of permutations? If I can find the function
;; to generate them ...

;; '(0 1 2 3 4 5 6 7 8 9)
;;                   - - rotate last 2
;; go until numbers no longer become bigger
;; then swap the last numbers

;; '(0 1 2 3 4 5 6 7 9 8)
;; '(0 1 2 3 4 5 6 8 7 9)
;; '(0 1 2 3 4 5 6 8 9 7)
;; '(0 1 2 3 4 5 6 9 7 8)
;; '(0 1 2 3 4 5 6 9 8 7)

;; '(0 0 0 0 0 0 0 0 0 0)
;; '(0 0 0 0 0 0 0 0 0 1)
;; '(0 0 0 0 0 0 0 0 1 0)
;; '(0 0 0 0 0 0 0 0 1 1)
;; '(0 0 0 0 0 0 0 1 0 0)

;;          *
;;         / \
;;        0   *
;;           / \
;;          1   *
;;             / \
;;            2   3

;; '(0 1 2)
;; '(0 2 1)
;; '(1 0 2)
;; '(1 2 0)
;; '(2 0 1)
;; '(2 1 0)

;; if the smallest number is the last -> something must be
;; swapped further at the front


(define permutations
  (sort (permute math:+decimal-digits+)
        (make-list-comparator <)))


(simple-format (current-output-port)
               "millionth permutation: ~a\n"
               (list-ref permutations (- (expt 10 6) 1)))