仅更改数组 Clisp 上的一个位置
Change just one position on array Clisp
我正在做一个基于 1 个 TSP 随机化 TSP（城市数组）的算法。
(do ((i 0 (+ i 1)))
((= i n-population))
(setf (aref population i) (shuffle TSP 100))
)
据我所知，我用 (shuffle TSP 100) 填充了数组 population 的 i 位置，每次迭代都调用了 (shuffle TSP 100)，但算法正在设置所有数组位置和不只是我的立场。
我怀疑是OP函数SHUFFLE的问题，还没有分享出来；我怀疑 SHUFFLE 正在对 *TSP* 数组本身进行混洗，而不是创建该数组的混洗副本。然后 POPULATION 值都引用同一个随机排列的 *TSP* 数组。
要解决这个问题，SHUFFLE 应该 return 一个打乱的数组，而不是就地打乱数组。这是一个对向量执行 Fisher-Yates 洗牌的函数：
(defun shuffle-vector (vect)
"Takes a vector argument VECT and returns a shuffled vector."
(let ((result (make-array (length vect) :fill-pointer 0)))
(labels ((shuffle (v)
(if (zerop (length v))
result
(let* ((i (random (length v)))
(x (elt v i)))
(vector-push x result)
(shuffle (concatenate 'vector
(subseq v 0 i)
(subseq v (1+ i))))))))
(shuffle vect))))
在 REPL 中测试：
CL-USER> (defvar *TSP* #("Village" "Town" "City" "Metropolis" "Megalopolis"))
*TSP*
CL-USER> (defvar *n-population* 5)
*N-POPULATION*
CL-USER> (defvar *population* (make-array *n-population*))
*POPULATION*
CL-USER> (dotimes (i *n-population*)
(setf (aref *population* i) (shuffle-vector *TSP*)))
NIL
CL-USER> *population*
#(#("Megalopolis" "City" "Metropolis" "Town" "Village")
#("Megalopolis" "Metropolis" "Town" "City" "Village")
#("City" "Megalopolis" "Town" "Village" "Metropolis")
#("City" "Megalopolis" "Village" "Metropolis" "Town")
#("Megalopolis" "Town" "Metropolis" "City" "Village"))
[注意。这个答案的早期版本包含一个错误，会严重改变洗牌的统计数据：请在下面查看更正版本和注释问题是。]
给定你的代码，稍微细化一下把它变成一个函数：
(defun fill-array-with-something (population n-population TSP)
(do ((i 0 (+ i 1)))
((= i n-population))
(setf (aref population i) (shuffle TSP 100))))
那么population从0到(1- n-population)的每个元素都会被设置为(shuffle TSP 100)的结果。那么有两种可能：
(shuffle TSP 100) returns 每次调用一个新对象；(shuffle TSP 100) returns 相同 对象 – 可能 TSP – 来自每次调用。
在第一种情况下，数组的每个元素都有一个不同的值。在第二种情况下，n-population 以下的所有元素将具有 相同的 值。
在不知道你的 shuffle 函数做什么的情况下，这里是一个会给出后一种行为的例子：
(defun shuffle (vec n)
;; shuffle pairs of elts of VEC, N times.
(loop with max = (length vec)
repeat n
do (rotatef (aref vec (random max))
(aref vec (random max)))
finally (return vec)))
我们可以测试这个：
> (let ((pop (make-array 10))
(tsp (vector 0 1 2 3 4 5 6 7 8 9 )))
(fill-array-with-something pop (length pop) tsp)
pop)
#(#(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6)
#(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6)
#(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6)
#(2 8 7 1 3 9 5 4 0 6))
如您所见，所有元素都神秘地相同，这是因为我的 shuffle 只是返回了它的第一个参数，并对其进行了适当的修改。
您可以通过显式检查 shuffle 的结果或例如使用 *print-circle* 查看共享来检查这一点。后一种方法非常巧妙：
> (let ((*print-circle* t)
(pop (make-array 10))
(tsp (vector 0 1 2 3 4 5 6 7 8 9 )))
(fill-array-with-something pop (length pop) tsp)
(print pop)
(values))
#(#1=#(4 6 7 0 1 2 5 9 3 8) #1# #1# #1# #1# #1# #1# #1# #1# #1#)
现在问题是什么一目了然。
解决方案是确保 shuffle returns 一个新的对象，或者复制它的结果。使用我的 shuffle 可以这样做：
(defun fill-array-with-something (population n-population tsp)
(do ((i 0 (+ i 1)))
((= i n-population))
(setf (aref population i) (shuffle (copy-seq TSP) 100))))
注意 这个答案的前一个版本有 (copy-seq (shuffle TSP 100))：对于我的 shuffle 版本，这是一个严重的错误，因为这意味着population 中的元素彼此相关，但随着您的进行，它们会变得越来越混乱。使用 (shuffle (copy-seq TSP) 100) 每个元素独立地获得相同数量的洗牌。
现在
> (let ((*print-circle* t)
(pop (make-array 10))
(tsp (vector 0 1 2 3 4 5 6 7 8 9 )))
(fill-array-with-something pop (length pop) tsp)
(print pop)
(values))
#(#(8 3 4 1 6 9 2 5 0 7) #(8 6 5 1 3 0 4 2 9 7) #(5 0 4 7 1 6 9 3 2 8)
#(3 0 7 6 2 9 4 5 1 8) #(8 2 5 1 7 3 9 0 4 6) #(0 5 6 3 8 7 2 1 4 9)
#(4 1 3 7 8 0 5 2 9 6) #(6 9 1 5 0 7 4 2 3 8) #(2 7 5 8 0 9 6 3 4 1)
#(5 4 8 9 6 7 2 0 1 3))
我正在做一个基于 1 个 TSP 随机化 TSP（城市数组）的算法。
(do ((i 0 (+ i 1)))
((= i n-population))
(setf (aref population i) (shuffle TSP 100))
)
据我所知，我用 (shuffle TSP 100) 填充了数组 population 的 i 位置，每次迭代都调用了 (shuffle TSP 100)，但算法正在设置所有数组位置和不只是我的立场。
我怀疑是OP函数SHUFFLE的问题，还没有分享出来；我怀疑 SHUFFLE 正在对 *TSP* 数组本身进行混洗，而不是创建该数组的混洗副本。然后 POPULATION 值都引用同一个随机排列的 *TSP* 数组。
要解决这个问题，SHUFFLE 应该 return 一个打乱的数组，而不是就地打乱数组。这是一个对向量执行 Fisher-Yates 洗牌的函数：
(defun shuffle-vector (vect)
"Takes a vector argument VECT and returns a shuffled vector."
(let ((result (make-array (length vect) :fill-pointer 0)))
(labels ((shuffle (v)
(if (zerop (length v))
result
(let* ((i (random (length v)))
(x (elt v i)))
(vector-push x result)
(shuffle (concatenate 'vector
(subseq v 0 i)
(subseq v (1+ i))))))))
(shuffle vect))))
在 REPL 中测试：
CL-USER> (defvar *TSP* #("Village" "Town" "City" "Metropolis" "Megalopolis"))
*TSP*
CL-USER> (defvar *n-population* 5)
*N-POPULATION*
CL-USER> (defvar *population* (make-array *n-population*))
*POPULATION*
CL-USER> (dotimes (i *n-population*)
(setf (aref *population* i) (shuffle-vector *TSP*)))
NIL
CL-USER> *population*
#(#("Megalopolis" "City" "Metropolis" "Town" "Village")
#("Megalopolis" "Metropolis" "Town" "City" "Village")
#("City" "Megalopolis" "Town" "Village" "Metropolis")
#("City" "Megalopolis" "Village" "Metropolis" "Town")
#("Megalopolis" "Town" "Metropolis" "City" "Village"))
[注意。这个答案的早期版本包含一个错误，会严重改变洗牌的统计数据：请在下面查看更正版本和注释问题是。]
给定你的代码，稍微细化一下把它变成一个函数：
(defun fill-array-with-something (population n-population TSP)
(do ((i 0 (+ i 1)))
((= i n-population))
(setf (aref population i) (shuffle TSP 100))))
那么population从0到(1- n-population)的每个元素都会被设置为(shuffle TSP 100)的结果。那么有两种可能：
(shuffle TSP 100)returns 每次调用一个新对象；(shuffle TSP 100)returns 相同 对象 – 可能TSP– 来自每次调用。
在第一种情况下，数组的每个元素都有一个不同的值。在第二种情况下，n-population 以下的所有元素将具有 相同的 值。
在不知道你的 shuffle 函数做什么的情况下，这里是一个会给出后一种行为的例子：
(defun shuffle (vec n)
;; shuffle pairs of elts of VEC, N times.
(loop with max = (length vec)
repeat n
do (rotatef (aref vec (random max))
(aref vec (random max)))
finally (return vec)))
我们可以测试这个：
> (let ((pop (make-array 10))
(tsp (vector 0 1 2 3 4 5 6 7 8 9 )))
(fill-array-with-something pop (length pop) tsp)
pop)
#(#(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6)
#(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6)
#(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6) #(2 8 7 1 3 9 5 4 0 6)
#(2 8 7 1 3 9 5 4 0 6))
如您所见，所有元素都神秘地相同，这是因为我的 shuffle 只是返回了它的第一个参数，并对其进行了适当的修改。
您可以通过显式检查 shuffle 的结果或例如使用 *print-circle* 查看共享来检查这一点。后一种方法非常巧妙：
> (let ((*print-circle* t)
(pop (make-array 10))
(tsp (vector 0 1 2 3 4 5 6 7 8 9 )))
(fill-array-with-something pop (length pop) tsp)
(print pop)
(values))
#(#1=#(4 6 7 0 1 2 5 9 3 8) #1# #1# #1# #1# #1# #1# #1# #1# #1#)
现在问题是什么一目了然。
解决方案是确保 shuffle returns 一个新的对象，或者复制它的结果。使用我的 shuffle 可以这样做：
(defun fill-array-with-something (population n-population tsp)
(do ((i 0 (+ i 1)))
((= i n-population))
(setf (aref population i) (shuffle (copy-seq TSP) 100))))
注意 这个答案的前一个版本有 (copy-seq (shuffle TSP 100))：对于我的 shuffle 版本，这是一个严重的错误，因为这意味着population 中的元素彼此相关，但随着您的进行，它们会变得越来越混乱。使用 (shuffle (copy-seq TSP) 100) 每个元素独立地获得相同数量的洗牌。
现在
> (let ((*print-circle* t)
(pop (make-array 10))
(tsp (vector 0 1 2 3 4 5 6 7 8 9 )))
(fill-array-with-something pop (length pop) tsp)
(print pop)
(values))
#(#(8 3 4 1 6 9 2 5 0 7) #(8 6 5 1 3 0 4 2 9 7) #(5 0 4 7 1 6 9 3 2 8)
#(3 0 7 6 2 9 4 5 1 8) #(8 2 5 1 7 3 9 0 4 6) #(0 5 6 3 8 7 2 1 4 9)
#(4 1 3 7 8 0 5 2 9 6) #(6 9 1 5 0 7 4 2 3 8) #(2 7 5 8 0 9 6 3 4 1)
#(5 4 8 9 6 7 2 0 1 3))