Re: Generation of permutations

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

<tmoran@acm.org> wrote in message
news:qD2C8.41$k97.25193567@newssvr13.news.prodigy.com...
>   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.

I *think* I follow - but that seems to disallow any sort of looping. (Or do
I misunderstand?) Isn't it possible for a program to be in a state it has
been in before (iterating through the data on disk again...) and not be
caught in an infininte loop? Or because you're including a check of the
state of the data as well, then it can't be in the same state plus the
identical state of the data without being caught in a loop? (So if you had
1k of program+data+processor_state, you'd save every bit, execute one clock
cycle, compare the 1k against every previous 1k and if it matches, its stuck
and throw it out? Sounds deliciously slow! :-)


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.

But that's just looking for the occurrence of a specific algorithm, isn't
it? Say I calculate the time needed for the Slow Sort algorithm
(permutations) to get through some data and use this as the worst case. I'd
reject every valid random algorithm that was T>Slow Sort. I'm sure I can
come up with valid code that sorts at a time greater than that of the Slow
Sort (Slow Sort plus delay (1.0), if nothing else.) So really, you're saying
"I want to see how long it takes to randomly generate at least the Slow Sort
algorithm." I can see that this works, but it seems sub-optimal. :-)

It might make a great article & example of tasking (One task sets the other
task to its sorting job & monitors the time, shooting it in the head &
restarting it as needed...) to implement something like this. :-)

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