algorithm - Common Lisp 代码卡住或需要优化

Question

作为我的 Common Lisp 学习例程的一部分，我目前正在处理 Project Euler 中的一些问题。符合那个网站的精神，我就不提是哪个问题了。

我遇到的问题是我的代码适用于小输入但卡住大输入。具体来说，它会卡住获得答案所需的相同数量级，但会成功运行低于该数量级的数量级。

问题描述如下:给定一组数字，形成这些数字的所有可能排列，然后对结果进行数字排序，并从结果集中选出第 n 个成员。

我将按如下方式运行下面的代码。

例如，如果我想获得数字的第 3 个排列 (1, 2, 3)，我会调用:

CL-USER>(数字排列 '(1 2 3) 3)
213

另一个例子是:

CL-USER>(数字排列 '(0 1 2 3 5) 100)
50231

代码适用于此:

CL-USER>(数字排列'(0 1 2 3 5 6 7 8)100)
1283675

但此调用卡住(或花费太长时间):

CL-USER>(数字排列'(0 1 2 3 5 6 7 8 9)1000000)

我的问题有两个。我在低效地做些什么导致计算花费这么长时间？我是否遇到了 Lisp 实现 (SBCL) 的某些限制？如何才能在合理的时间内完成计算？

代码:

;;; How to make permutations of a list
;;;
;;;   all permutations of a list L is:
;;;   for each element E in L:
;;;   that element prepended to all permutations of [ L with E removed ]
(defun permutation (digits)
  ;if the list is null or empty, return NIL
  (cond ((null digits) nil)
    ;if the list consists of one element, return the list of one element
    ((null (cdr digits)) (list digits))
    ; cycle through every element in list and append            
        ; that element to all permutations of a list of elements
    ; with the current element removed
    (t (loop for element in digits
          append (mapcar (lambda (l) (cons element l))
                 (permutation (remove element digits)))))))

(defun list-to-number (list)
  (loop for item in list for i from (- (list-length list) 1) downto 0
        summing (* (expt 10 i) item)))

(defun number-permutations (digits n)
  (car (nthcdr (- n 1)
         (sort (loop for item in (permutation digits)
                     collecting (list-to-number item))
               #'<))))

Answer 1

如 High Performance Mark 的评论所述，所以这个问题可以关闭:

我做错了什么导致计算花费这么长时间？
您进行 n! 计算，n 是数字的数量。 1000000! 大致等于 8.26×10^5565708(请参阅 Quora 以获得很好的解释)，难怪你的计算机无法处理它；)

我是否遇到了 Lisp 实现 (SBCL) 的某些限制？
也许吧，但您的 RAM 最有可能是第一个失败的东西。

怎样才能让计算在合理的时间内完成？
做另一个计算。欧拉计划练习的重点通常是找到解决问题的聪明方法，而不是蛮力解决问题。

祝你好运!