LISP check if the list is symmetric without reverse

Question

Does anyone have ideas on how to do this ... the converse is too slow, and I want to avoid using a function.

Basically, I want to be able to return true if something like '(abba) appears or' (abcdcba)

and false for something asymmetric

Answer 1

I am not sure why using REVERSE not effective enough; did you really profile the solution? You just go through the list once to do this; same as (let's say) find the length of a list, and then you can go through two lists once for comparison.

If you would like to be a little favorite, you could simultaneously find the length of the list and cancel it with LOOP as follows:

 (defun fancier-palindrome-p (list) (let ((reversed '()) (length 0)) (dolist (elt list) (incf length) (push elt reversed)) (dotimes (i (floor length 2) t) (unless (eql (pop list) (pop reversed)) (return nil))))) 

This allows you to skip half of the checks. I do not think it is worth the extra complexity. You can also use the move down the list with a turtle and a hare to save half the cost due to even greater complexity.

  (defun ridiculous-palindrome-p (list) (let ((reversed-front '())) (loop :for tortoise :on list :for hare :on list :by #'cddr :until (null (cdr hare)) :do (push (car tortoise) reversed-front) :finally (return (if (null hare) ; length is even (equal tortoise reversed-front) (equal (cdr tortoise) reversed-front)))))) 

None of these decisions seem more convincing to me than

 (defun palindrome-p (list) (equal list (reverse list)) 

If this is really a bottleneck, you might be better off using vectors as a sequence representation to take advantage of fast random access, for example:

 (defun vector-palindrome-p (vector) (let* ((n (length vector)) (jn)) (dotimes (i (floor n 2) (return t)) (unless (eql (aref vector i) (aref vector (decf j))) (return nil))))) 

Answer 2

Isn't that a good decision? Or you can search for other solutions using "palindrome lisp" as keywords in your favorite search engine.

Answer 3

This function avoids using reverse:

 (defun palindromp (a) (or (null a) (null (cdr a)) (and (equal (car a) (car (last a))) (palindromp (butlast (cdr a)))))) 

Answer 4

Here is CommonLisp:

 (defun pali (l) (labels ((scan (vnl) (or (>= n (/ l 2)) (and (equal (elt vn) (elt v (- ln 1))) (scan v (+ n 1) l))))) (scan (apply #'vector l) 0 (length l)))) 

Have you used ' labels ' before !? Here you go (in Scheme):

 (define (palindrome? l) (let scanning ((v (list->vector l)) (n 0) (len (length l))) (or (>= n (/ len 2)) (and (equal? (vector-ref vn) (vector-ref v (- len n 1))) (scanning v (+ n 1) len))))) 

Answer 5

 (defun pal() (format t "enter list") (setf list1(read)) (print list1) (setf list2(rev list1)) (if (equal list1 list2) (print "palindrome") (print "not palindrome"))) (reverse (list1) (setf list2 nil) (do ((i 1 (+ i 1)))((equal list1 nil) (format t "reverse list") (print list2)) (setf list2 (cons (car list1) list2)) (setf list1 ( cdr list1))))