列表的组合列表

Question

你好，我必须在 lisp 中编写这个函数：

(defun combine-list-of-lsts (lst)...)

所以当执行函数时我应该得到

(combine-list-of-lsts '((a b c) (+-) (1 2 3 4)))

((A + 1) (A + 2) (A + 3) (A + 4) (A-1) (A-2) (A-3) (A-4) (B + 1) (B + 2) (B + 3) (B + 4) (B-1) (B-2) (B-3) (B-4)(C + 1) (C + 2) (C + 3) (C + 4) (C-1) (C-2) (C-3) (C-4))

我现在拥有的是：

(defun combine-list-of-lsts (lst)
(if (null (cdr lst))
    (car lst)
(if (null (cddr lst))
        (combine-lst-lst (car lst) (cadr lst))
(combine-lst-lst (car lst) (combine-list-of-lsts (cdr lst))))))

使用这个辅助功能：

(defun combine-lst-lst (lst1 lst2)
        (mapcan #'(lambda (x) (combine-elt-lst x lst2)) lst1))

(defun combine-elt-lst (elt lst)
            (mapcar #'(lambda (x) (list elt x)) lst))

但是我得到的是：

((A (+ 1)) (A (+ 2)) (A (+ 3)) (A (+ 4)) (A(-1)) (A(-2)) (A(-3)) (A(-4))...)

我不知道怎么做但是没有括号

Answer 1

首先要看这个案例：

(合并列表列表'((a b c)))

那应该是什么？也许不是你的函数 returns...
那我就看看函数combine-list-of-lsts。您需要两个 IF 语句吗？
再看combine-elt-lst。您真的要使用 LIST 吗？它创建一个新列表。将元素添加到前面不是更有意义吗？

Answer 2

通常，当你想将多个参数化简为一个结果时，你需要函数#'reduce。您的列表组合名称为笛卡尔 n 元积。

以下函数：

(defun cartesian (lst1 lst2)
  (let (acc)
    (dolist (v1 lst1 acc)
      (dolist (v2 lst2)
        (push (cons v1 v2) acc)))))

创建两个提供的列表的笛卡尔积作为 conses 列表，其中 #'car 是 lst1 的一个元素，#'cdr 是 lst2 的一个元素。

(cartesian '(1 2 3) '(- +))

==> ((3 . -) (3 . +) (2 . -) (2 . +) (1 . -) (1 . +))

但是请注意，在此类产品上调用 #'cartesian 会 return 格式错误的结果 - 缺点和元素的缺点：

(cartesian (cartesian '(1 2) '(+ -)) '(a))

==> (((1 . +) . A) ((1 . -) . A) ((2 . +) . A) ((2 . -) . A))

发生这种情况，因为第一组的成员是conses，而不是atoms。另一方面，列表由cons组成，如果我们颠倒创建产品的顺序，我们可以更接近扁平列表，我们的目标是什么：

(cartesian '(1 2)
           (cartesian '(+ -) '(a)))

==> ((2 + . A) (2 - . A) (1 + . A) (1 - . A))

要创建正确的列表，我们只需要用 nil 对每个产品进行 cons - 换句话说，创建另一个产品。

(cartesian '(1 2)
           (cartesian '(+ -)  
                      (cartesian '(a) '(nil))))

==> ((2 + A) (2 - A) (1 + A) (1 - A))

总结一切：您需要以相反的顺序创建连续列表的笛卡尔积，最后一个是 '(nil)，这可以通过 reduce 表达式实现。最终代码将如下所示：

(defun cartesian (lst1 lst2)
  (let (acc)
    (dolist (v1 lst1 acc)
      (dolist (v2 lst2)
        (push (cons v1 v2) acc)))))

(defun combine-lsts (lsts)
  (reduce
   #'cartesian
   lsts
   :from-end t
   :initial-value '(nil)))

Answer 3

您还可以尝试另一种方法，

(defun mingle (x y)
 (let ((temp nil))
  (loop for item in x do
   (loop for it in y do
    (cond ((listp it) (setf temp (cons (append (cons item 'nil) it) temp)))
     (t (setf temp (cons (append (cons item 'nil) (cons it 'nil)) temp))))))
  temp))

用法：(mingle '(c d f) (mingle '(1 2 3) '(+ -))) =>

((F 1 +) (F 1 -) (F 2 +) (F 2 -) (F 3 +) (F 3 -) (D 1 +) (D 1 -) (D 2 +) (D 2 -) (D 3 +) (D 3 -) (C 1 +) (C 1 -) (C 2 +) (C 2 -) (C 3 +) (C 3 -))

列表的组合列表

Combining list of list

lisp

list

common-lisp