The Robinson-Schensted Algorithm

Description of the problem

I am not going to delve too much into explaining today’s problem. I am going to write an implementation of the Schensted Algorithm in common lisp.  This algorithm gives us one side of the Robinson–Schensted correspondence. Essentially, it creates a Young tableaux from a given permutation.

Implementation

First, I am going to need a utility function:

(defun locate (x xs &optional ys)
  (cond ((null xs)
         (list nil (append (reverse ys) (list x))))
        ((< x (car xs))
         (list (car xs) (append (reverse ys) (list x) (cdr xs))))
        (t (locate x (cdr xs) (cons (car xs) ys)))))
LOCATE

This function inserts a number \(x\) into an ordered list replacing the smallest number in the list larger than \(x\).

(locate 3 '(0 1 2 4 5 6))
(4 (0 1 2 3 5 6))

Now, the code below implements the insertion part of the Schensted’s algorithm:

(defun insert (x xs &optional ys)
  (if (null x)
     (append ys xs)
     (destructuring-bind (a bs)
         (locate x (car xs))
       (insert a (cdr xs) (append ys (list bs))))))
INSERT

Let me test it with the example on wikipedia:

(insert 4 '((1 2 5 7) (3 8)))
((1 2 4 7) (3 5) (8))

And now, the main part of the algorithm.

(defun robinson–schensted (zs)
  (let (res)
    (dolist (z zs res)
      (setf res (insert z res)))))
ROBINSON–SCHENSTED

However, in order to test it I m going to need a function that returns a random permutation:

(defun random-permutation (xs)
   (let ((n (length xs)))
      (mapcar #'car
              (sort (mapcar (lambda (x) (cons x (random n))) xs)
                    #'<
                    :key #'cdr))))
RANDOM-PERMUTATION

Let me test the random permutation code:

(random-permutation '(1 2 3 4))
(2 4 1 3)

(random-permutation '(1 2 3 4))
(1 2 4 3)

And finally, the test of the algorithm

(let ((perm (random-permutation (loop for i from 1 to 9 collect i))))
   (list perm (robinson–schensted perm)))
((8 4 9 2 5 6 7 1 3) ((1 3 6 7) (2 5) (4 9) (8)))