The Kitchen Sink and Other Oddities

Atabey Kaygun

Havel–Hakimi Algorithm in Clojure

Description of the problem

Yesterday I wrote an implementation of Havel-Hakimi in common lisp. Today I’ll do an implementation in clojure.

Implementation

Here is the implementation in clojure:

(defn havel-hakimi [xs]
  (loop [ys xs]
    (cond (empty? ys) true
          (odd? (reduce + ys)) false
          :else (recur (->> (repeat (- (count ys) (first ys) 1) 0)
                            (concat (repeat (first ys) 1))
                            (map - (rest ys))
                            (remove #{0})
                            sort)))))
#'user/havel-hakimi

Let us test on the same sequences I tested yesterday:

(havel-hakimi [3 3 3 3])
(havel-hakimi [1 2 3 4])
true
false

And here is the large example:

(havel-hakimi [1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 5 5 6])
true