CODEWITHSUNDEEP
lispcommon-lisp
miguel__frtt
miguel__frtt

Reputation: 73

Change just one position on array Clisp

I'm doing an algorithm that randomizes a TSP (array of citys) based on 1 TSP.

(do ((i 0 (+ i 1)))
    ((= i n-population))
        (setf (aref population i) (shuffle TSP 100))
    )

And as far as I know im filling up i positions of the array population with (shuffle TSP 100) that is beeing called each iteration, but the algorithm is setting all array positions and not just i position.

Upvotes: 0

Views: 87

Answers (2)

user5920214
user5920214

Reputation:

[Note. An earlier version of this answer contained a mistake which would badly alter the statistics of the shuffling: please check below for the corrected version and a note as to what the problem was.]

Given your code, slightly elaborated to turn it into a function:

(defun fill-array-with-something (population n-population TSP)
  (do ((i 0 (+ i 1)))
      ((= i n-population))
    (setf (aref population i) (shuffle TSP 100))))

Then each element of population from 0 to (1- n-population) will be set to the result of (shuffle TSP 100). There are then two possibilities:

  • (shuffle TSP 100) returns a fresh object from each call;
  • (shuffle TSP 100) returns the same object – probably TSP – from each call.

In the first case, each element of the array will have a distinct value. In the second case, all elements below n-population will have the same value.

Without knowing what your shuffle function does, here is an example of one which will give the latter behaviour:

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

And we can test this:

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

As you can see all the elements are mysteriously the same thing, which is because my shuffle simply returned its first argument, having modified it in place.

You can check this by either explicitly checking the result of shuffle, or by, for instance, using *print-circle* to see the sharing. The latter approach is pretty neat:

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

And now it's immediately apparent what the problem is.

The solution is to make sure either that shuffle returns a fresh object, or to copy its result. With my shuffle this can be done like this:

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

Note that a previous version of this answer had (copy-seq (shuffle TSP 100)): with my version of shuffle this is a serious mistake, as it means that the elements in population are related to each other but get increasingly shuffled as you go along. With (shuffle (copy-seq TSP) 100) each element gets the same amount of shuffling, independently.

And now

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

Upvotes: 2

ad absurdum
ad absurdum

Reputation: 21358

I suspect that the problem is in OP function SHUFFLE which has not yet been shared; my suspicion is that SHUFFLE is shuffling the *TSP* array itself in place instead of creating a shuffled copy of that array. The POPULATION values are then all referencing the same shuffled *TSP* array.

To solve this problem, SHUFFLE should return a shuffled array instead of shuffling the array in place. Here is a function that performs a Fisher-Yates shuffle on a vector:

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

Testing in the 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"))

Upvotes: 2

Related Questions