Sort a list by joining neighboring elements with +

sort-by-joinin-with-plus

;;;;
;; Sort a list by joining neighboring elements with `+'
;; This is in exponential time.
;;
;; Pseudo-code:
;;
;; Function "join" (list, max-join-count, join-count) ->
;;     Fail if join-count is greater than max-join-count.
;;     If the list looks sorted return join-count.
;;     For Each number In List
;;         Recur (list with current and next number joined, max-join-count, join-count + 1)
;;
;; Function "best-join" (list) ->
;;     max-join-count = 0
;;     while not join (list, max-join-count++)

(defn join-ahead [f i v]
  (concat (take i v)
          [(f (nth v i) (nth v (inc i)))]
          (drop (+ 2 i) v)))

(defn sort-by-joining
  "Sort a list by joining neighboring elements with `+'"
  ([v max-join-count join-count]
     (if (or (nil? max-join-count)
             (<= join-count max-join-count))
       (if (or (empty? v)
               (= v (sort v)))
         {:vector v :join-count join-count}
         (loop [i 0]
           (when (< (inc i) (count v))
             (let [r (sort-by-joining (join-ahead + i v)
                                      max-join-count
                                      (inc join-count))]
               (or r (recur (inc i)))))))))
  ([v max-join-count]
     (sort-by-joining v max-join-count 0))
  ([v]
     (sort-by-joining v nil 0)))

(defn fewest-joins [v]
  (loop [i 0]
    (if (sort-by-joining v i)
      i
      (recur (inc i)))))

(deftest test-fewest-joins
  (is (= 0 (fewest-joins nil)))
  (is (= 1 (fewest-joins [4 6 5 3 9])))
  (is (= 6 (fewest-joins [1 9 22 90 1 1 1 32 78 13 1]))))

(deftest test-sort-by-joining
  (is (= {:vector nil         :join-count 0} (sort-by-joining nil)))
  (is (= {:vector [1 2 3 4 5] :join-count 0} (sort-by-joining [1 2 3 4 5])))
  (is (= {:vector [4 6 8 9]   :join-count 1} (sort-by-joining [4 6 5 3 9] 1)))
  (is (= {:vector [1]         :join-count 0} (sort-by-joining [1])))
  (is (nil?                                  (sort-by-joining [4 6 5 3 9] 0)))
  (is (not (nil?                             (sort-by-joining [1 9 22 90 1 1 1 32 78 13 1] 6))))
  (is (nil?                                  (sort-by-joining [1 9 22 90 1 1 1 32 78 13 1] 5))))

(deftest test-join-ahead
  (is (= [1 5]     (join-ahead + 1 [1 2 3])))
  (is (= [3 3]     (join-ahead + 0 [1 2 3])))
  (is (= [1 2 3 9] (join-ahead + 3 [1 2 3 4 5]))))

;;(run-tests)