Randomly merging two listst uniformly at random in clojure

random_merge.clj

;; Most implementations of a random merge between two lists don't give equal chance to 
;; each of the possible interleavings. The following approach is able to produce such
;; a result by adapting the (almost correct) algoritm shown at [1]. An important part
;; of the algorithm was generating a sorted list of size `N` uniformly at random. An 
;; efficient algorithm for this is presented at [2].
;; [1]: https://stackoverflow.com/questions/4577882/how-to-merge-2-sorted-listed-into-one-shuffled-list-while-keeping-internal-order
;; [2]: https://math.stackexchange.com/questions/3218854/randomly-generate-a-sorted-set-with-uniform-distribution

(defn rand-subset
  "Returns a u.a.r k-subset of {1,..,n}"
  [n, k]
  (cond
    (= k 0) #{}
    :else (if (< (rand) (/ k n))
            (conj (rand-subset (dec n) (dec k)) (dec n))
            (rand-subset (dec n) k))))

(defn random-sorted-list
  "Returns a u.a.r list with values in range [1..`max-val`] and given `size`"
  [max-val, size]
  (map-indexed
   (fn [index, val]
     (- val index))
   (sort
    (rand-subset (+ max-val size -1) size))))

(defn insert-at-v
  "Inserts `element` at position `pos` of vector `v`"
  [v, pos, element]
  (vec (concat (subvec v, 0, pos)
               [element]
               (subvec v, pos))))

(defn random-merge
  "Randomly interleaves two or more lists in such a way that
  any possible interleaving is equally likely"
  ([A, B & rest]
   (apply random-merge (random-merge A B) rest))
  ([A, B]
   (let [positions (vec (random-sorted-list (count B) (count A)))]
     (reduce
      (fn [merged, i]
        (insert-at-v merged, (+ i (positions i)), (A i)))
      B
      (range (count A))))))

(comment

  ;; Here we can see how the distribution indeed looks uniform
  (frequencies (repeatedly 10000 #(random-merge [1 2 3] [:a :b :c])))

  )