Add 'subsequences' and 'permutations' to Data.List (ticket #1990)

[Yitzchak Gale]

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