331 - PurelyFunctional.tv - https://purelyfunctional.tv/issues/purelyfunctional-tv-newsletter-331-tool-shadow-cljs/

00 Generating random, sorted lists.md

generating sorted lists

In the technique #2 above, we generate a sorted list. But how do we do that?

This week’s challenge is to come up with ideas how we might do that. Don’t worry if your idea is crazy. The intent is to engage your brain and get thinking about how to generate values.

Here are two I’ll just throw out there to plant a seed:

1. Generate random lists and throw out unsorted ones. (Clearly, this won’t work, but that’s okay! I’ll throw it out there anyway.)
2. Generate random lists and sort them. (Is this cheating? It doesn’t matter. I’m putting it out there.)

Eric Normand.clj

(def gen-sorted-list
  (gen/fmap
   (fn [[init nums]]
     (next (reductions + init nums)))
   (gen/tuple gen/long (gen/vector gen/nat))))

Magnus Kvalevag.clj

(require '[clojure.test.check.clojure-test :refer [defspec]]
         '[clojure.test.check.properties :as prop])

(defn sorted-list-gen
  "Generate a list by recursively adding elements that should come after the previous element.
   Arguments
    - next-el-gen: a function that returns a generator that produces the next element in the list.
                   The function must have two arities defined:
                    - arity-0 returns a generator for the first element
                    - arity-1 takes the current element and returns a generator for the next element"
  ([next-el-gen]
   (gen/sized
     (fn [s]
       (gen/let [list-length (gen/choose 0 s)               ; The length of the generated list is based on the generator size
                 first-el    (next-el-gen)]                 ; Set the first element in the list
         (sorted-list-gen next-el-gen list-length 0 first-el)))))
  ([next-el-gen list-length n x]
   (if (>= n list-length)
     (gen/return '())                                       ; Return empty list after "list-length" recursions.
     (gen/let [next-x      (next-el-gen x)                  ; The element coming after x
               sorted-list (sorted-list-gen next-el-gen list-length (inc n) next-x)] ; Recursive call with next element
       (cons x sorted-list)))))                             ; The current element is in front of the the list containing the next elements

(defn next-int-gen
  ([] gen/int)
  ([x] (gen/let [some-natural-number gen/nat]
         (+ some-natural-number x))))

(defspec sorted-list-gen-generates-sorted-lists 1000
  (prop/for-all [l (sorted-list-gen next-int-gen)]
    (= (sort l) l)))

(gen/let [random-increments (gen/vector gen/nat)]
  (letfn [(sum-n [n]
            (->> (take n random-increments) (reduce + 0)))]
    (->> (range 0 (count random-increments))
         (map (comp sum-n inc)))))

Mark Champine.clj

;;;;;; Some ways to generate sorted lists

;;;; 1. Repeatedly apply non-negative deltas
(defn genrndnseq [l n]
  (repeatedly l #(rand-int n)))

(reductions + (genrndnseq 10 5))
;; (2 4 7 7 7 11 12 13 16 18)
;; (3 4 7 7 11 14 15 17 21 24)

;;;; 2. Build sorted list via ordered insertions
(defn insert-in-order [c v]
  (let [[split-left split-right] (split-with #(< % v) c)]
    (concat split-left (list v) split-right)))

(reduce insert-in-order '() (genrndnseq 10 100))
;; (12 13 25 37 48 56 67 81 87 92)

;;;; 3. Prepend iff <= min, append iff >= max
;; Note: poor behavior with random inputs:
;;   sparse, innefficient, and length indeterminate
(defn min-pre-max-app [c v]
  (cond
    (empty? c) (list v)
    (>= v (last c)) (concat c (list v))
    (<= v (first c)) (concat (list v) c)
    :default c))

;; random input
(reduce min-pre-max-app '() (genrndnseq 100 100))
;; (0 1 7 95 99 99)
;; (2 3 5 5 14 50 52 54 64 71 80 84 97 99)

;; optimal input - all included in sorted output
(reduce min-pre-max-app '() '(11 5 2 15 88))
;; (2 5 11 15 88)

;; pessimal input - only 2 included in sorted output
(reduce min-pre-max-app '() '(88 15 17 66 24 25 26 26 28))
;; (15 88)

;;;; 4. Apply any monotnic function to the integers
(def integers (iterate inc 0))

(defn mf1 [n] (* 2 n))
(take 10 (map mf1 integers))
;; (0 2 4 6 8 10 12 14 16 18)

(defn mf2 [n] (* n n))
(take 10 (map mf2 integers))
;; (0 1 4 9 16 25 36 49 64 81)

(defn mf3 [n] (Math/sqrt n))
(take 5 (map mf3 integers))
;; (0.0 1.0 1.4142135623730951 1.7320508075688772 2.0)

(defn mf4 [n] (Math/log n))
(take 10 (map mf4 (map inc integers)))
;; (0.0 0.6931471805599453 1.0986122886681098 1.3862943611198906 1.6094379124341003 1.791759469228055 1.9459101490553132 2.0794415416798357 2.1972245773362196 2.302585092994046)

;;;; 5. Similar to 4 but iterate instead of mapping ints

;; Repeatedly multiply by a fraction slighly greater than 1
(->> (iterate #(* % (+ 1 (rand 0.1))) 100)
     (map int)               ;; the rest is just prettification
     (map (partial + -99))
     (rest)
     (take 10))

;; a few runs
;; (7 16 27 32 43 54 62 63 66 72)
;; (1 8 10 11 16 20 22 22 29 31)
;; (3 9 16 27 33 38 39 42 44 55)

;;;; 6. Ordered combinations of sorted lists are sorted
(for [i (sort (genrndnseq 3 10))
      j (sort (genrndnseq 4 10))
      k (sort (genrndnseq 3 10))]
  (Integer. (str i j k)))

;; (441 444 449 441 441 448 472 473 473 481 483 484 500 502 506 522 526 527 542 547 549 572 576 578 820 823 825 852 857 858 871 875 876 890 894 895)

Teodor Heggelund.clj

(defn gen-random-sorted [start nextstep length]
  (take length (iterate nextstep start)))

(defn random-sorted-ints [length]
  (gen-random-sorted (rand-int 10)
                     (fn [previous]
                       (+ previous (rand-int 10)))
                     length))

(random-sorted-ints 10)
;; => (9 11 18 25 32 34 35 36 40 49)

(defn random-sorted-floats [length]
  (gen-random-sorted (rand) #(+ % (rand)) length))

(random-sorted-floats 10)
;; => (0.6244334359496073
;;     1.0741412346775956
;;     1.0769678992043148
;;     1.8851457407374048
;;     2.6436578165710745
;;     2.9312770861357738
;;     3.47262023409804
;;     3.813648216802071
;;     4.665080862846675
;;     4.686839966735484)

(defn random-char []
  (let [lower (int \a)
        upper (int \z)]
    (char (+ lower (rand-int (inc (- upper lower)))))))

(defn random-sorted-strings [length]
  (gen-random-sorted ""
                     (fn [previous]
                       (str previous (random-char)))
                     length))

(random-sorted-strings 10)
;; => ("" "z" "zt" "ztq" "ztqu" "ztqun" "ztqunu" "ztqunud" "ztqunudi" "ztqunudic")