[Haskell-cafe] permutations and performance
gale at sefer.org
Sun Aug 17 11:27:05 EDT 2008
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:
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
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.
More information about the Haskell-Cafe