OrderedBits

Efficient ordered (by popcount) enumeration of bits

https://github.com/choener/OrderedBits

Stackage Nightly 2022-01-25: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
This version can be pinned in stack with:OrderedBits-0.0.2.0@sha256:cdfad9211ece1c6be245f8d7068600c5524756adf2981c6f1f679bd55d697486,2623

Module documentation for 0.0.2.0

Used by 1 package in nightly-2021-07-23(full list with versions):

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/

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