search

elm-community / list-extra

Convenience functions for working with List.
http://package.elm-lang.org/packages/elm-community/list-extra/latest
MIT License
135 stars 59 forks source link

Permutation Memory Issues #60

Open Chadtech opened 7 years ago

Chadtech commented 7 years ago

In the slack channel, Numiastowski discovered that permutations causes a memory problem. A list of 9 elements might have as many as 9! permutations, and therefore, 9! stack calls.

I believe this can be solved by implementing something like this: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm, or any non-recursive permutation function.

But before settling on that, we should consider use cases of the permutation function. Has anyone used it? How did you use it? What problem did it solve for you?

pzp1997 commented 7 years ago

Maybe it should be lazy?

Chadtech commented 7 years ago

@zwilias made this cool Ellie app demonstrating an implementation of the next permutation algorithm. Could be useful to this project : https://ellie-app.com/3vnrtbJffbYa1/0

pzp1997 commented 7 years ago

We might want to consider the implementation of subsequences as well, which outputs a list of 2n lists for an input list of length n.