Havel–Hakimi Algorithm in Common-Lisp

Description of the problem

A degree sequence is a non-decreasing sequence \((d_1\leq \cdots\leq d_n)\) of positive integers such that there is a graph whose vertices are labelled with \(1,\ldots,n\) with \(\deg(i) = d_i\). Erdős–Gallai theorem gives a necessary and sufficient condition that a given non-increasing sequence is a degree sequence. However, there is a very simple recursive algorithm called Havel–Hakimi algorithm that determines if a given non-increasing sequence is a degree sequence. Today, I’ll implement Havel-Hakimi in common lisp.

The Implementation

Here is my implementation:

(defun havel-hakimi (xs)
  (cond
    ((null xs) t)
    ((oddp (reduce #'+ xs)) nil)
    (t (havel-hakimi (delete 0 (sort (mapcar #'-
                                             (cdr xs)
                                             (append (loop repeat (car xs) collect 1)
                                                     (loop repeat (- (length xs) (car xs) 1) collect 0)))
                                     #'<))))))

HAVEL-HAKIMI

And here are some tests:

(havel-hakimi '(3 3 3 3))
(havel-hakimi '(1 2 3 4))

T
NIL

Here is a large sequence to test:

(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))

T