OrderedBits

Efficient ordered (by popcount) enumeration of bits

https://github.com/choener/OrderedBits

LTS Haskell 23.26:0.0.2.0
Stackage Nightly 2025-06-29: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

Used by 1 package in nightly-2022-01-25(full list with versions):
PrimitiveArray

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