Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Quriosity: SLOW way to sort :-)

Author: Tord Romstad

Date: 13:18:11 10/20/99

Go up one level in this thread


On October 19, 1999 at 07:51:27, Jari Huikari wrote:

>How to make the most ineffective sort? Here is one proposition:
>
>1. Randomly swap two members of the list
>2. if list is in order stop, else goto 1.
>
>Or try all (N!) possible orders, and choose the right one.
>
>May work fast anyway, if the list is short.
>
>					Jari

A Common Lisp implementation of the second algorithm suggested:

(defun generate-all-permutations (list)
  (cond
   ((<= (length list) 1) (list list))
   (t (apply #'append
	(let ((permutations nil))
	  (dolist (elt list permutations)
	    (push (mapcar #'(lambda (l) (cons elt l))
	          	  (generate-all-permutations
			   (remove elt list :count 1)))
		  permutations)))))))

(defun sorted-p (list)
  (apply #'< list))

(defun bogosort (list comparison-p)
  (let ((permutations (generate-all-permutations list)))
    (find-if #'sorted-p permutations)))

My function for generating all permutations is terribly ugly, but the program
works and I am too tired to think about anything better...   :-)

Tord



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.