Re: Generation of permutations

[tmoran@acm.org]

> start running at instruction 0. Did the data set on disk get sorted? No? Go
> back to filling memory again.
>...
>So did the program get stuck in an infinite loop or is it just taking a
>*really* long time to sort the data?
  As Dewar points out, you just keep snapshots of all the states the
program has gone through and check for "Hey!  We've been here before!".
Your RAM + disk have a finite number of bits N so there are at most 2**N
possible states it can wander among.  If the instruction execution time is
t, it can't run more than t*2**N without repeating itself.  Or you can
calculate how long T some standard sort algorithm would take, maximum,
then abort if your randomly generated program is still running at T+1 sec.
If your random program generator will create all possible configurations
of RAM, then one of those is going to be identical to the standard sort
algorithm and eventually you are going to come across it, guaranteed.  If
there are N bits in RAM, this is guaranteed to take no more than
(T+1)*2**N.  And you may get lucky and find a better random program
sooner.  Slow, yes, but not interminable.  ;)

> assuming that one of the rules of slow sorting is that you
> guarantee the algorithm will eventually result in a sorted list of data.
  If no individual random program is allowed to run forever,
and your random generator generates all possible programs in your
finite machine, then
      loop
        generate random program;
        run it till done or it's in a loop or it's been running T seconds;
        exit when sorted;
      end loop;
is indeed guaranteed to sort your data in a finite, albeit long, time.
  You can do a similar thing to generate a general sort program.
      loop
        generate random program;
        appears_successful := true;
        for all possible sets of data on your disk loop
          run it till done or it's in a loop or it's been running T seconds;
          if not data_is_sorted then
            appears_successful := false;
            exit;
          end if;
        end loop;
        exit when appears_successful;
      end loop;
This too must terminate in a finite time, giving you a general sort
program that will work on any set of data on your disk.