quickperm算法的clisp实现

Question

我正在研究 n 皇后问题的迭代解决方案。我决定将状态 space 表示为 0 和 1 的数组，这样 1 就代表女王的存在。计划是生成数组的所有排列，然后编写一个验证器来修剪不正确的解决方案。我正在尝试这样做是常见的 lisp，即使我在今天之前从未接触过函数式编程。

为了生成排列，我选择使用第一个伪代码示例尝试并实现此算法：http://www.quickperm.org/

这是我的尝试：

(defun permute (n)
  (setf total (* n n)) 
  (let ((a (make-array total :initial-element 0))      ;list of objects to permute
       (p (make-array total :initial-element 0)))     ;array to control iteration 
    (dotimes (i n) (setf (aref a i) 1))
    (loop for index from 1 while (< index total) do
      (setf (aref p index) (- (aref p index) 1))      ;decrement p[i] by 1
      (if (= (rem index 2) 1)                         ;if index is odd
          (setf j (aref p index))                     ;j = p[index]
          (setf j 0))                                 ;else j = 0
      (rotatef (aref a index) (aref a j))             ;swap a[index] & a[j]
      (setf index 1)                                  ;index = 1 
      (loop while (= (aref p index) 0) do             ;while p[index] == 0
        (setf (aref p index) index)                   ;p[index] = i
        (setf index (+ index 1)))                     ;index++
      print a)))           
(permute 4)

目前，我收到错误：AREF: index -1 for #array，这似乎是由 (setf (aref p index) (- (aref p index) 1)) 行引起的。在伪代码中，该行似乎实现了 p[index] = p[index] - 1。这是我唯一的减法操作，但它不应该对索引本身进行操作，而只是对其所在位置的值进行操作。

我错过了什么？

编辑：我将 p 的每个元素初始化为 0。每个元素实际上应该等于它的索引。将 post 完成后更新代码。

Answer 1

这是最终产品，以防哪天有什么伤心的事情在这里跌跌撞撞。

(defun permute (n) 
  (let ((a (make-array n))                            ;list of objects to permute
       (p (make-array (+ 1 n))))                      ;array to control iteration 
    (dotimes (i n) (setf (aref a i) (+ i 1)))
    (dotimes (i (+ n 1)) (setf (aref p i) i)) 
    (setf index 1)
    (loop while (< index n) do
      (setf (aref p index) (- (aref p index) 1))      ;decrement p[i] by 1
      (if (= (rem index 2) 1)                         ;if index is odd
          (setf j (aref p index))                     ;j = p[index]
          (setf j 0))                                 ;else j = 0
      (rotatef (aref a index) (aref a j))             ;swap a[index] & a[j]
      (setf index 1)                                  ;index = 1 
      (loop while (= (aref p index) 0)  do            ;while p[index] == 0
        (setf (aref p index) index)                   ;p[index] = i
        (setf index (+ index 1)))                     ;index++
      (verif a n))))

Answer 2

好久没写 CL 了，这里有一个使用了一些惯用形式的版本。

(defun permute (n) 
  (let ((a (make-array n))                        ;list of objects to permute
       (p (make-array (1+ n))))                   ;array to control iteration 
    (dotimes (i n) (setf (aref a i) (1+ i)))
    (dotimes (i (1+ n)) (setf (aref p i) i))
    (setf i 1)
    (loop with i = 1 and j = 0 while (< i n) do
      (decf (aref p i))                           ;decrement p[i] by 1
      (setf j (if (oddp i) (aref p i) 0))         ;j = odd(i) ? a[i] : 0
      (rotatef (aref a i) (aref a j))             ;swap a[i] & a[j]
      (setf i 1)                                  ;i = 1 
      (loop while (zerop (aref p i)) do           ;while p[i] == 0
        (setf (aref p i) i)                       ;p[i] = i
        (incf i))                                 ;index++
      (verif a n))))

quickperm算法的clisp实现

Clisp implementation of quickperm algorithm

permutation

common-lisp

indexoutofboundsexception