Re: Generation of permutations

[tmoran@acm.org]

> "Marin David Condic" > A better (slower) algorithm would be > to
> generate a random set of machine
> > instructions, execute them, see if it sorted the list
>
> You could see if it sorted some particular list, but to
> determine whether a set of instructions constitutes a
> general sorting algorithm is obviously recursively
> undecidable. So this is not a well formed method.
  I tried an experiment*: the data is three letters chosen from 'a' .. 'c',
the instructions are for a machine with instructions: compare and skip
if greater, swap, jump, and stop.  Generating random 16 line programs,
and random data strings, and aborting any program still running after
50 instruction cycles, there were 125801 successes in 874199 tries.
Testing each of the successful programs against all possible combinations
of three letters from 'a' .. 'c', 9 of the programs successfully sorted
all combinations, ie, were general routines capable of sorting any
input data in their universe.
  So "recursively undecidable" is a fancy way of saying it may get stuck
in an infinite loop, and, assuming he didn't mean to allow that, mcondic's
algorithm is perfectly good as a (slow) sorting algorithm.
  * Program available on request.