Genetic algorithms

Hey guys, i'm learning a bit of IA and i want to make a traveling salesman problem using GA .
So i have a doubt , i have some points pre-defined ex:

(defvar a '(23 20))
(defvar b '(10 30))
(defvar c '(0 45))
(defvar d '(43 0))

How can i randomly create a list that contain all of it elements only one time ? I think some ways that wouldn't be very fast .

What are the elements of the list? I imagine a destructive shuffle would be fast enough—but that's assuming you already have a list for shuffling.

You can randomize it with sort:

(defparameter *lst* (list a b c d)) ; list of the elements
(setf *lst* 
  (sort *lst* 
        (lambda (&rest lst) 
          (< 0.5 (random 1.0)))))

sylwester wrote:You can randomize it with sort:

(defparameter *lst* (list a b c d)) ; list of the elements
(setf *lst* 
  (sort *lst* 
        (lambda (&rest lst) 
          (< 0.5 (random 1.0)))))

That code seems work,but how exactly that work?

Domus123 wrote:

sylwester wrote:You can randomize it with sort:

(defparameter *lst* (list a b c d)) ; list of the elements
(setf *lst* 
  (sort *lst* 
        (lambda (&rest lst) 
          (< 0.5 (random 1.0)))))

That code seems work,but how exactly that work?

It won't work with every sorting algorithm. With something like quicksort, you're partitioning the sequence recursively and rearranging each partition around some pivot element—with a random predicate, the pivot is irrelevant, of course. So it's like flipping a coin to decide whether to swap around a given element within the partition. Personally, I'd use a Fisher-Yates shuffle, which is like playing Bingo:

(defun shuffle (list)
  (loop for tail on list
        for n downfrom (list-length list) above 1
        do (rotatef (car tail) (nth (random n) tail))
        finally (return list)))

I was actually surprised by it too, because the C++ sort is allowed to crash if your items comparison changes between calls. I wouldn't have even thought of doing it this way, but I checked the hyperspec and:

This is guaranteed even if the predicate does not really consistently represent a total order (in which case the elements will be scrambled in some unpredictable way, but no element will be lost)

Since that's exactly what is wanted here using RANDOM with SORT is fine.