如何在 lisp 中生成一个笛卡尔积？

Question

这是我生成笛卡尔积的代码：

(defun cartesian-product (LIST)
  (LOOP FOR X IN LIST
    NCONC
        (LOOP FOR Y IN LIST
         COLLECT (LIST X Y))))

我试着用这个输出一个笛卡尔积：

(defun cartesian-product-generator (CALLBACK LIST)
  (LOOP FOR X IN LIST
    NCONC
        (LOOP FOR Y IN LIST
        DO(FUNCALL CALLBACK (LIST X Y)))))

但是当我尝试使用以下方法测试时出现错误：

(cartesian-product-generator '(A B C))

Error: Too few arguments in call to #<Compiled-function cartesian-product-generator #x30200097E60F>:
       1 argument provided, at least 2 required.  While executing: cartesian-product-generator, in process listener(1).

我是 LISP 的新手，想知道为什么会出现错误以及如何修复此错误。最后，我想在每次调用函数时输出每个笛卡尔积。

例如，如果列表包含 ((1 1) (1 2) (2 1) (2 2))。我想生成 (1 1)。然后(1 2)。然后(2 1)。最后，(2 2).

Answer 1

您可能希望通过 quicklisp 查看 cl-coroutine 库。那么你的 cartesian-product 可以写成

(cl-coroutine:defcoroutine cartesian-product (list)
  (loop for x in list
    do (loop for y in list
      do (cl-coroutine:yield (list x y)))))

示例用法可以是：

(cl-coroutine:with-coroutine (cartesian-product)
  (let ((x (list 1 2 3)))
    (loop for y = (cartesian-product x)
      while y do (print y))))

; outputs (1 1) (1 2) ... (3 3)

Answer 2

您的第一个代码确实可以正常工作。

(defun cartesian-product (list)
  (loop
    for x in list
    nconc (loop for y in list
                collect (list x y))))

用 '(a b c) returns 列表调用它：

((A A) (A B) (A C) (B A) (B B) (B C) (C A) (C B) (C C))

您想避免构建列表并改用回调。为了简化，首先尝试只打印元素而不是收集它们。

这意味着你不关心返回生成的值取决于调用者：您只想生成它们并将它们打印为尽快上架。

基本上，您可以将所有nconc和collect关键字替换为do，并添加对print的调用：

(defun cartesian-product (list)
  (loop
    for x in list
    do (loop for y in list
             do (print (list x y)))))

使用 '(a b c) 对 REPL 进行快速测试应该打印相同的内容元素和以前一样，每个元素都在一个单独的行上。

现在，您可以概括 print 并调用任何您想要的东西：

(defun map-cartesian-product (function list)
  (loop
    for x in list
    do (loop for y in list
             do (funcall function (list x y)))))

只是想看看它是否仍然有效，请进行快速测试：

(map-cartesian-product #'print '(a b c))

这应该具有与以前相同的行为。

因为你只是为了副作用而遍历一个列表，你可以使用 DOLIST:

(defun map-cartesian-product (function list)
  (dolist (x list)
    (dolist (y list)
      (funcall function (list x y)))))

同样，您可以测试它是否仍像以前一样工作。

Answer 3

只想在这里留下我的 2 美分。

您也可以使用宏来完成此操作

(defmacro cartesian-product (lists)
  (let* ((indices (loop for i from 1 to (length lists)
                        collect (gensym (format nil "~a-i-" i))))
         (initial-value `(loop for ,(car (last indices)) in ',(car (last lists))
                               collect `(,,@indices))))
    (reduce
     (lambda (x y)
       `(loop for ,(car x) in ',(cadr x)
              nconc ,y))
     (mapcar #'list (butlast indices) (butlast lists))
     :from-end t
     :initial-value initial-value)))

扩展为

(cartesian-product ((H P) (a b c) (1 2 3 5)))

至

(loop for #:|1-i-806| in '(h p)
      nconc (loop for #:|2-i-807| in '(a b c)
                  nconc (loop for #:|3-i-808| in '(1 2 3 5)
                              collect `(,#:|1-i-806| ,#:|2-i-807| ,#:|3-i-808|))))

结果为

((H A 1) (H A 2) (H A 3) (H A 5) (H B 1) (H B 2) (H B 3) (H B 5) (H C 1) (H C 2) (H C 3) (H C 5)
 (P A 1) (P A 2) (P A 3) (P A 5) (P B 1) (P B 2) (P B 3) (P B 5) (P C 1) (P C 2) (P C 3) (P C 5))

我喜欢它，因为它非常简单，不需要递归。

如何在 lisp 中生成一个笛卡尔积？

How to generate one cartesian product in lisp?

lisp

loops

generator

common-lisp

cartesian-product