I wrote:
So when we subtract out the control, satisfying the consistency property increases run time by at least a factor of 3.
Twan van Laarhoven wrote:
What exactly are you calculating here?
The cost of the logic that actually generates the permutations, after subtracting off the cost of adding up 10! lists of 10 numbers, which is an artifact of our ad hoc performance test. True, we also subtract off the cost of iterating over all of those copies, which, due to laziness, is shared somewhat with the generating algorithm. But that sharing is common to all algorithms, so I think this is fair. Anyway, no need to dwell on this point. It is not so relevant anymore, see below.
The property is nice, but is it worth that penalty? I'm not sure, I'd be interested in hearing other people's opinions.
No one else responded. I am taking that as support for the consistency condition and Twan's approach. Besides, after Twan's further progress, there is hardly a penalty anymore (less than a factor of 2 even according to my logic, if you accept it). As one further sanity check, let's see if we are re-inventing the wheel by checking Knuth. The relevant chapter is Volume 4, section 7.2.1.2, published in Volume 4 Fascicle 2. There is no link to this on Knuth's home page anymore, so I won't link to it either due to copywrite concerns. But let's just say that for those who, like me, have no access to a printed copy of Knuth, Google "knuth permutations" >>= I'm feeling lucky gets you there as of this writing. So, yes, of course, we have re-invented the wheel. But Twan seems to have done quite a good job of it. First of all, permutations3 is essentially Knuth's Algorithm P. As far as Knuth knows, that algorithm was first published by English church bell ringers in the 1600's. So it is quite appropriate for the present season. Knuth's Algorithm G is a general method of generating algorithms that satisfy our consistency condition. The algorithms are parametrized over decompositions of the group structure of the permutation group into Sims tables. Unfortunately, it is not clear which of these many algorithms is Twan's permutations8, nor is it clear (to me) from Knuth which one of them would be fastest. But I agree with Twan that permutations8 must be close to optimal. Regards, Yitz