OrderedBits: Efficient ordered (by popcount) enumeration of bits

[ bsd3, data, library ] [ Propose Tags ]

This library provides efficient methods to enumerate all elements of a set in order of the population count, or the ordered enumerations of the elements of the powerset of a set. First, the empty set, then all 1-element sets, all 2-element sets, etc. Such enumerations are important for algorithms over unordered data sets. Examples include the travelling salesman problem and the closely related Hamiltonian path problem.


[Skip to Readme]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.0.0.1, 0.0.0.2, 0.0.0.3, 0.0.1.0, 0.0.1.1, 0.0.1.2, 0.0.2.0
Change log changelog.md
Dependencies base (>=4.7 && <4.9), bits (>=0.4 && <0.5), primitive (>=0.5 && <0.7), QuickCheck (>=2.7 && <2.9), vector (>=0.10 && <0.11), vector-algorithms (>=0.6 && <0.7.1) [details]
License BSD-3-Clause
Copyright Christian Hoener zu Siederdissen, 2014 - 2015
Author Christian Hoener zu Siederdissen
Maintainer choener@bioinf.uni-leipzig.de
Category Data
Home page https://github.com/choener/OrderedBits
Bug tracker https://github.com/choener/OrderedBits/issues
Source repo head: git clone git://github.com/choener/OrderedBits
Uploaded by ChristianHoener at 2015-07-14T14:29:20Z
Distributions LTSHaskell:0.0.2.0, NixOS:0.0.2.0, Stackage:0.0.2.0
Reverse Dependencies 4 direct, 33 indirect [details]
Downloads 6040 total (29 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2015-07-14 [all 1 reports]

Readme for OrderedBits-0.0.0.2

[back to package description]

Build Status

OrderedBits

The OrderedBits library provides methods to generate unboxed vectors of Ints (and others) ordered by their population count or Hamming distance to the 0 set. In other words, we enumerate the power set of a given input set.

Such an order is important for dynamic programming algorithms for Hamiltonian path problems and the travelling salesman problem.

Contact

Christian Hoener zu Siederdissen
Leipzig University, Leipzig, Germany
choener@bioinf.uni-leipzig.de
http://www.bioinf.uni-leipzig.de/~choener/