From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.4 required=5.0 tests=AC_FROM_MANY_DOTS,BAYES_00
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,c42dbf68f5320193
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-05-03 15:08:35 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.icl.net!diablo.netcom.net.uk!netcom.net.uk!psiuk-p2!psiuk-p3!uknet!psiuk-n!news.pace.co.uk!nh.pace.co.uk!not-for-mail
From: "Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>
Newsgroups: comp.lang.ada
Subject: Re: Generation of permutations
Date: Fri, 3 May 2002 09:04:38 -0400
Organization: Posted on a server owned by Pace Micro Technology plc
Message-ID: <aau1t7$kq6$1@nh.pace.co.uk>
References: <aajce7$7jb$1@snipp.uninett.no>
 <4519e058.0204300552.15317df9@posting.google.com>
 <aam989$99c$1@nh.pace.co.uk>
 <4519e058.0205020747.11336b44@posting.google.com>
 <3CD1664A.804F56BC@attbi.com>
NNTP-Posting-Host: dhcp-200-133.miami.pace.co.uk
X-Trace: nh.pace.co.uk 1020431079 21318 136.170.200.133 (3 May 2002 13:04:39
 GMT)
X-Complaints-To: newsmaster@news.cam.pace.co.uk
NNTP-Posting-Date: 3 May 2002 13:04:39 GMT
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 5.50.4522.1200
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4522.1200
Xref: archiver1.google.com comp.lang.ada:23515
Date: 2002-05-03T13:04:39+00:00
List-Id: <comp.lang.ada>

Yeah, but in effect that's just generating random permutations of the data
instead of ordered permutations. If you want to guarantee that you actually
end up with an answer, you have to do something with your PRNG that makes
sure it would generate all permutations, so, on average it would perform the
same as generating ordered permutations.

A better (slower) algorithm would be to generate a random set of machine
instructions, execute them, see if it sorted the list and quit when it does.
The problem, of course, is that you can't guarantee that it will ever
finish.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com


"Mark Biggar" <mark.a.biggar@attbi.com> wrote in message
news:3CD1664A.804F56BC@attbi.com...
>
> There are worse sorts then Bogosort.  For example there is 52-pickup
> sort: repeatedly randomize the list until you notice that it
> is sorted.
>