这个lisp函数可以递归实现吗? [英] Can be this lisp function be implemented recursively?

问题描述

此功能的目标是生成2个列表的笛卡尔积. 例如

The goal of this function is to generate the cartesian product of 2 list. For example

• (组合(列表1 2 3)(列表4 5))=>(1 4)(1 5)(2 4)(2 5)(3 4)(3 5)

• (combo (list 1 2 3) (list 4 5)) => (1 4) (1 5) (2 4) (2 5) (3 4) (3 5)

(defun combo (l1 l2)
(let    (
            (res (list))
        )
    (dolist (elem1 l1 res)
        (dolist (elem2 l2 res)
            (setq res (append res (list(list elem1 elem2))))
        )
    )
)

)

如何递归实现?

推荐答案

一个简单的递归实现将是使用两个辅助函数.一个遍历L1(下面代码中的%COMBO)，调用另一个函数将一个元素与L2(%PRODUCT)中的每个元素配对:

A simple recursive implementation would be to use two helper functions; one to traverse through L1 (%COMBO in the code below), calling another function to pair an element with each element from L2 (%PRODUCT):

(defun combo (l1 l2)
  (labels ((%product (el list &optional (acc (list)))
             (if (endp list)
                 acc
                 (%product el (rest list) (cons (list el (first list)) acc))))
           (%combo (l1 l2 &optional (acc (list)))
             (if (endp l1)
                 (nreverse acc)
                 (%combo (rest l1) l2 (nconc (%product (first l1) l2) acc)))))
    (%combo l1 l2)))

尽管如此，迭代方法既简单又有效.您不必在循环中使用APPEND，而应该在末尾反转列表.

The iterative approach is both simpler and more efficient though. Instead of using APPEND in a loop, you should just reverse the list at the end.

(defun combo (l1 l2)
  (let ((res (list)))
    (dolist (e1 l1 (nreverse res))
      (dolist (e2 l2)
        (push (list e1 e2) res)))))

您还可以只使用亚历山大中的MAP-PRODUCT函数:

You could also just use the MAP-PRODUCT function from Alexandria:

CL-USER> (ql:quickload :alexandria)
;=> (:ALEXANDRIA)
CL-USER> (use-package :alexandria)
;=> T
CL-USER> (map-product #'list (list 1 2 3) (list 4 5))
;=> ((1 4) (1 5) (2 4) (2 5) (3 4) (3 5))

这篇关于这个lisp函数可以递归实现吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！