OrderedBits

Efficient ordered (by popcount) enumeration of bits

https://github.com/choener/OrderedBits

LTS Haskell 22.17:0.0.2.0
Stackage Nightly 2024-04-14:0.0.2.0
Latest on Hackage:0.0.2.0

See all snapshots OrderedBits appears in

BSD-3-Clause licensed by Christian Hoener zu Siederdissen
Maintained by [email protected]
This version can be pinned in stack with:OrderedBits-0.0.2.0@sha256:cdfad9211ece1c6be245f8d7068600c5524756adf2981c6f1f679bd55d697486,2623

Module documentation for 0.0.2.0

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
[email protected]
http://www.bioinf.uni-leipzig.de/~choener/

Changes

0.0.2.0

  • subsequences of a given mask

0.0.1.4

  • added bitmasks

0.0.1.3

  • tests with ghc 8.2.x

0.0.1.2

  • removed upper bounds

0.0.1.1

  • move to tasty framework for property tests

0.0.1.0

  • moved all properties directly into tests/properties.hs

0.0.0.3

  • vector <= 0.11 supported (with conditional compilation)

0.0.0.2

  • vector-algorithms version bump
  • removed explicit llvm flag (use –ghc-options)

0.0.0.1

  • initial checkin of the (naive) sorted implementation
  • memoization of Int-sets up to 31 bit
  • non-memo versions (somewhat efficient)
  • travis-ci integration