John D. Ramsdell <[EMAIL PROTECTED]> 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
