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.
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)))))
LOCATEThis 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))))))
INSERTLet 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–SCHENSTEDHowever, 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-PERMUTATIONLet 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)))