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.