クイックパーペムアルゴリズムのClisp実装

Question

私はクイーンズ問題の反復解法を研究しています。私は状態空間を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を実装しているようです。これは私が持っている唯一の減算演算ですが、その位置の値だけでインデックス上で操作するべきではありません。

私には何が欠けていますか？

EDIT：pのすべての要素を0に初期化しました。各要素は、実際にそのインデックスと等しいと考えられます。完了したら更新されたコードを投稿します。

Answer 1

は、私が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)))) 

Answer 2

ここで最終的な製品があります。何か悲しいサップがいつかここで遭遇する場合があります。

(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))))