[Haskell-cafe] permutations and performance

[Yitzchak Gale]

John D. Ramsdell <ramsdell0 at gmail.com> wrote:
> I tried to replace a permutation generator with one that generates
> each permutation from the previous one, in a stream-like fashion.  I
> had hoped the stream-based algorithm would be more efficient because I
> use only one permutation at a time, so only the permutation and the
> previous one need be in memory at one time.  I thought I'd share the
> results of testing the two algorithms.

Yes, thanks for the interesting discussion.

You may also be interested in the following recent thread:

http://www.haskell.org/pipermail/libraries/2007-December/008788.html

There, Twan van Laarhoven designs the implementation
of the permutations function that is slated to be included in
GHC 6.10. That implementation is pretty well tweaked for speed,
while satisfying the following condition suggested by
David Benbennick:

map (take n) (take (factorial n) $ permutations [1..]) == permutations [1..n]

It's also interesting that this function has an unusually long history
for computer science. Some of the best algorithms were first
discovered by English church bell ringers nearly 400 years ago.
Knuth discusses permutations in Volume 4 Fascicle 2.

Regards,
Yitz