Как можно объединить две строки, которые расположены в алфавитном порядке в LISP с помощью рекурсии
Я учу Лисп. Я реализовал общую функцию lisp, которая объединяет две строки, которые упорядочены в алфавитном порядке с использованием рекурсии. Вот мой код, но что-то не так, и я не понял этого.
(defun merge (F L)
(if (null F)
(if (null L)
F ; return f
( L )) ; else return L
;else if
(if (null L)
F) ; return F
;else if
(if (string< (substring F 0 1) (substring L 0 1)
(concat 'string (substring F 0 1) (merge (substring F 1 (length F)) L)))
(
(concat 'string (substring L 0 1) (merge F (substring L 1 (length L)) ))
))))
Изменить: я просто хочу объединить две строки, такие как; входными данными являются строка a = adf и строка b = beg, и результат или результат должны быть такими; abdefg
Заранее спасибо.
4 ответа
Судя по вашим комментариям, похоже, что вы пытаетесь использовать if с рядом условий (как ряд else ifна некоторых других языках). Для этого вы, вероятно, хотите cond.
Я заменил это if с cond и убрал некоторые другие ошибки, и это сработало.
(defun empty (s) (= (length s) 0))
(defun my-merge (F L)
(cond
((empty F)
(if (empty L)
F
L))
((empty L)
F)
(t
(if (string< (subseq F 0 1) (subseq L 0 1))
(concatenate 'string (subseq F 0 1) (my-merge (subseq F 1 (length F)) L))
(concatenate 'string (subseq L 0 1) (my-merge F (subseq L 1 (length L))))))))
Ваш тестовый пример вышел так, как вы хотели:
* (my-merge "adf" "beg")
"abdefg"
С помощью string< это перебор, char< следует использовать вместо этого, как показано Kaz. Перерасчет length на каждом этапе этот алгоритм должен быть квадратичным, поэтому его следует избегать. С помощью sort "подделка" делает его O(n log n) вместо O(n). С помощью concatenate 'string все время, вероятно, влечет за собой дополнительные расходы на ненужные обходы тоже.
Вот естественное рекурсивное решение:
(defun str-merge (F L)
(labels ((g (a b)
(cond
((null a) b)
((null b) a)
((char< (car b) (car a))
(cons (car b) (g a (cdr b))))
(t (cons (car a) (g (cdr a) b))))))
(coerce (g (coerce F 'list) (coerce L 'list)) 'string)))
Но Common Lisp не имеет гарантии оптимизации хвостовых вызовов, не говоря уже о гарантии оптимизации хвостовой рекурсии по модулю минусов (даже если последний был описан еще в 1974 году с использованием "Lisp 1.6". rplaca а также rplacd операторы присваивания полей "). Поэтому мы должны вручную закодировать это как цикл:
(defun str-merge (F L &aux (s (list nil)) )
(do ( (p s (cdr p))
(a (coerce F 'list) (if q a (cdr a)))
(b (coerce L 'list) (if q (cdr b) b))
(q nil))
( (or (null a) (null b))
(if a (rplacd p a) (rplacd p b))
(coerce (cdr s) 'string))
(setq q (char< (car b) (car a)))
(if q
(rplacd p (list (car b)))
(rplacd p (list (car a))))))
Было довольно много хороших ответов, так зачем мне добавлять еще один? Что ж, ниже, вероятно, более эффективно, чем другие ответы здесь.
(defun merge-strings (a b)
(let* ((lena (length a))
(lenb (length b))
(len (+ lena lenb))
(s (make-string len)))
(labels
((safe-char< (x y)
(if (and x y) (char< x y)
(not (null x))))
(choose-next (x y)
(let ((ax (when (< x lena) (aref a x)))
(by (when (< y lenb) (aref b y)))
(xy (+ x y)))
(cond
((= xy len) s)
((safe-char< ax by)
(setf (aref s xy) ax)
(choose-next (1+ x) y))
(t
(setf (aref s xy) by)
(choose-next x (1+ y)))))))
(choose-next 0 0))))
(merge-strings "adf" "beg")
Он более эффективен именно в смысле выделения памяти - он только выделяет достаточно памяти для записи строки результата, никогда ничего не приводит к принуждению (из списка в строку или из массива в строку и т. Д.). Это может выглядеть не очень красиво, но это потому, что он пытается сделать каждый расчет только один раз.
Это, конечно, не самый эффективный способ написания этой функции, но программирование абсолютно без эффективности не поможет вам продвинуться далеко вперед.
Рекурсивный способ сделать это (исправлено в соответствии с комментарием - другие решения также могут получить форму IF).
(defun merge-strings (a b)
(concatenate 'string
(merge-strings-under a b)))
(defun merge-strings-under (a b)
(when (and
(= (length a)
(length b))
(> (length a) 0))
(append (if (string< (aref a 0) (aref b 0))
(list (aref a 0) (aref b 0))
(list (aref b 0) (aref a 0)))
(merge-strings-under (subseq a 1)
(subseq b 1)))))
Вот итерационный способ сделать это.
(concatenate 'string
(loop for i across "adf" for j across "beg" nconc (list i j)))
Обратите внимание, что они основаны на построении строки в списке символов, а затем векторизации (строка является вектором символов).
Вы также можете написать более C-esque подход...
(defun merge-strings-vector (a b)
(let ((retstr (make-array (list (+
(length a)
(length b)))
:element-type 'character)))
(labels ((merge-str (a b i)
(when (and
(= (length a)
(length b))
(/= i (length a)))
(setf (aref retstr (* 2 i)) (aref a i))
(setf (aref retstr (1+ (* 2 i))) (aref b i))
(merge-str a b (1+ i)))))
(merge-str a b 0)
retstr)))
Обратите внимание, что этот - в отличие от других 2 - имеет побочные эффекты в функции. Это также, имхо, сложнее понять.
Все 3 имеют различное количество циклов для выполнения на SBCL 56; Кажется, каждый из них занимает от 6 до 11 тысяч в большинстве моих испытаний. Я не уверен почему.