# 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
```