我已经有了生成元素列表的所有排列的代码。然而，我意识到，如果我想操作生成的列表，我需要遍历这个列表。该列表可能会很大，因此维护成本很高。我想知道是否有一种方法可以通过每次调用生成排列，以便我可以检查列表是否与我需要的匹配，如果不匹配，我将生成下一个排列。 （每次该函数都会一次返回一个列表。）

My code:

(defun allPermutations (list) 
  (cond
     ((null list)  nil) 
     ((null (cdr list))  (list list)) 
     (t  (loop for element in list 
               append (mapcar (lambda (l) (cons element l))
                              (allPermutations (remove element list))))))) 

一般原则

假设您有以下内容range功能：

(defun range (start end &optional (step 1))
  (loop for x from start below end by step collect x))

您可以接受另一个参数，一个函数，并为每个元素调用它：

(defun range-generator (callback start end &optional (step 1))
  (loop for x from start below end by step do (funcall callback x)))

这使调用者可以控制迭代过程：

(block root
  (range-generator (lambda (v)
                     (print v)
                     (when (>= v 10)
                       (return-from root)))
                   0 300))


0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10

See RETURN, BLOCK.

排列

如果您想避免分配太多内存，您可以安排代码分配中间数据结构once并在每次调用回调时重用它们。这是一个带注释的示例：

(defun permutations% (list callback)
  (when list
    (let* (;; Size of input list
           (size (length list))

           ;; EMPTY is a sentinel value which is guaranteed to
           ;; never be equal to any element from LIST.
           (empty (gensym "SENTINEL"))

           ;; Working vector containing elements from LIST, or
           ;; EMPTY. This vector is mutated to remember which
           ;; element from the input LIST was already added to the
           ;; permutation.
           (items (make-array size :initial-contents list))

           ;; Working vector containing the current
           ;; permutation. It contains a FILL-POINTER so that we
           ;; can easily call VECTOR-PUSH and VECTOR-POP to
           ;; add/remove elements.
           (permutation (make-array (length items) :fill-pointer 0)))

      ;; Define a local recursive function named POPULATE, which
      ;; accepts a COUNT argument. The count starts at SIZE and
      ;; decreases at each recursive invocation, allowing the
      ;; function to know when it should end.
      (labels ((populate (count)
                 (if (plusp count)
                     ;; Loop over ITEMS by index
                     (dotimes (item-index size)
                       (let ((item (svref items item-index)))
                         ;; We found an ITEM which is not yet
                         ;; present in PERMUTATION.
                         (unless (eq item empty)
                           ;; Push that element
                           (vector-push item permutation)
                           ;; Replace current value in ITEMS by EMPTY
                           (setf (svref items item-index) empty)

                           ;; POPULATE will recursively populate
                           ;; the remaining elements in
                           ;; PERMUTATION and call CALLBACK. Once
                           ;; it is done, it will return here.
                           (populate (1- count))

                           ;; There are other items to process in
                           ;; current loop. Reset the state to how
                           ;; it was before calling POPULATE.

                           ;; Replace the EMPTY value by the
                           ;; original ITEM at current index.
                           (setf (svref items item-index) item)

                           ;; Remove ITEM from PERMUTATION.
                           (vector-pop permutation))))

                     ;; We filled PERMUTATION with SIZE elements.
                     ;; Call CALLBACK with PERMUTATION. Note: the
                     ;; callback function is always given the same
                     ;; vector, but its content changes over
                     ;; time. The value passed to CALLBACK is thus
                     ;; valid only during the time we are
                     ;; executing CALLBACK. If the caller needs to
                     ;; keep a copy of the current permutation, it
                     ;; should COPY-LIST the value.
                     (funcall callback permutation))))

        ;; Initiate recursive function with current SIZE.
        (populate size)))))

该函数接受一个列表和一个回调，这是一个接受一个参数（当前排列）的函数。注意该参数仅在动态范围调用的，因为一旦调用返回，传递给回调的相同数据结构就会被修改。

如上所述，您可以调用任何函数，特别是引用词法环境中其他变量的闭包。这里，匿名 lambda 递增count变量，它允许计算排列的数量，而不将它们存储在列表中并获取列表的大小：

(time
 (let ((count 0))
   (permutations% '(a b c d e f g h i j k) (lambda (p) (incf count)))
   count))
=> 39916800

Evaluation took:
  6.455 seconds of real time
  6.438200 seconds of total run time (6.437584 user, 0.000616 system)
  99.74% CPU
  17,506,444,509 processor cycles
  0 bytes consed

在上述报告中，0 字节消耗表示分配的内存的大致数量（不包括堆栈分配）。 您还可以提供该函数的更安全版本，该函数在将每个排列发送到回调函数之前复制每个排列。

(defun permutations (list callback)
  (permutations% list (lambda (permutation)
                        (funcall callback (coerce permutation 'list)))))

See also

也可以看看威尔·尼斯的回答，它设法用列表处理剩余元素的集合，从而避免了过滤 EMPTY 元素的需要。