Re: Generation of permutations

["Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org>]

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.
>