I worked quite a bit today on the permutations program for my research project. Thank God I had very few problems writing the program. No mysterious bugs popped up, no unexplainable behavior. So, I now have it running several hundred thousand iterations of a simple block sorting algorithm to get an idea of the performance.
I don't know how much mileage I'll be able to get out of computerized testing. Running exhaustive searches only works for small permutations, and Monte Carlo methods for large permutations aren't exhaustive. What hurts are the numbers I'm getting:
After 40,000 iterations using permutations with 1,000 numbers, the average number of steps to sort a permutation is 761.0, and the largest number of steps is 825. With 1,000,000 iterations of permutations of size 100 I got 84 as the maximum number of steps.
The very worst algorithm, a 3-approximation, takes n steps with permutations of size n. This "good" algorithm is averaging 0.76n and going as high as 0.84n. There are several possible reasons:
- Most permutations don't have many 2- or 3-reductions.
- This algorithm is in fact very poor.
- Dammit, as soon as I started writing up this list my head went blank.