subsets

This package provides two modules that allow to efficiently iterate over all subsets of any list. Here is a quick code example:

>>> data T = A | B | C deriving (Show)
>>> subsetsAsc [A, B, C] 0 3
[[], [A], [B], [C], [A, B], [A, C], [B, C], [A, B, C]]
>>> subsetsDesc [A, B, C] 3 3
[[A,B,C],[B,C],[A,C],[A,B],[C],[B],[A],[]]

The idea of the Banker's sequence is used to achieve this. This concept in described in Loughry, van Hemert, Schoofs, 2002 although no implementation details suggested in the paper are being used.

This approach has the following upsides:

• No class constraints
• Subsets are generated without recursion thus being very memory efficient; you will need a constant amount of memory throughout your iteration
• Subsets are generated in sorted order concerning their subset-order which in some scenarios can save a lot of time

Subsets are generated by mapping index lists to some given list. The subset generation itself does not have any significant overhead and runs in O(2^n*n) (which corresponds to the number of elements in all subsets). Only the lookup adds performance overhead. Therefore the functions subsetsAsc and subsetsDesc run in O(2^n*n*log(n)).

If you want to implement custom mappers you can either use the index set returned by indexSetsAsc/indexSetsDesc or directly provide a mapper function to mapIndexSetsAsc/mapIndexSetsDesc. Confer the inline documentation for more details and type annotations.

Contributing

You use stack to build the library and run tests. I'm always happy to receive issues and/or pull requests.

References

Loughry, Joe & van Hemert, Jano & Schoofs, L. (2002).
Efficiently Enumerating the Subsets of a Set.
https://www.researchgate.net/publication/2526315_Efficiently_Enumerating_the_Subsets_of_a_Set