Safe Haskell | None |
---|---|

Language | Haskell2010 |

Efficiently enumerate the bits in data types in order of population
count. This yields, say, `000, 001, 010, 100, 011, 101, 110, 111`

(or
`0, 1, 2, 4, 3, 5, 6, 7`

). Another view is of looking at the bits as
a bitset, first enumerating the empty set, then all 1-element sets, all
2-element sets, up to the set size.

The enumerator can be inlined with `unfoldr`

(of the `vector`

package)
and is a good producer.

A memo-table is available, since `popCntSorted`

is still waiting for an
efficient `popCntEnumerated`

that does not require sorting.

- lsbZ :: Ranked t => t -> Int
- nextActiveZ :: Ranked t => Int -> t -> Int
- maybeNextActive :: Ranked t => Int -> t -> Maybe Int
- maybeLsb :: Ranked t => t -> Maybe Int
- popPermutation :: Ranked t => Int -> t -> Maybe t
- popComplement :: Ranked t => Int -> t -> t
- popCntSorted :: (Unbox n, Integral n, Bits n, Ranked n) => Int -> Vector n
- popCntMemoInt :: Int -> Vector Int
- popCntMemoWord :: Int -> Vector Word
- popShiftL :: Ranked t => t -> t -> t
- popShiftR :: Ranked t => t -> t -> t
- activeBitsL :: Ranked t => t -> [Int]
- activeBitsS :: (Ranked t, Monad m) => t -> Stream m Int
- activeBitsV :: (Ranked t, Vector v Int) => t -> v Int

# Documentation

nextActiveZ :: Ranked t => Int -> t -> Int Source #

Given the currently active bit `k`

and the set `t`

, get the next
active bit. Return `-1`

if there is no next active bit.

popPermutation :: Ranked t => Int -> t -> Maybe t Source #

Enumerate all sets with the same population count. Given a population
`i`

, this returns `Just j`

with `j>i`

(but same number of set bits) or
`Nothing`

. For a population count of `k`

, start with `2^(k+1) -1`

.

Note that `sort permutations == sort (nub permutations)`

if
`permutations`

is a set of all permutations for a given `popCount`

generated by `popPermutation`

. The `Data.List.permutations`

functions
will create duplicates.

cf http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

popComplement :: Ranked t => Int -> t -> t Source #

Given a population, get the complement. The first argument is the size of the population (say. 8 for 8 bits); the second the current population.

Examples:

`>>>`

28`popComplement 5 (3 :: Int)`

`>>>`

60`popComplement 6 (3 :: Int)`

popCntSorted :: (Unbox n, Integral n, Bits n, Ranked n) => Int -> Vector n Source #

The *slow* default implementation. We sort the vector, not the list,
as sorting will walk the whole data structure anyway, and the vector
requires not as much memory.

Replaced `popCount &&& id`

as sort, which provides for `a<b`

on equal
`popCount`

with `popCount &&& activeBitsL`

which sorts according to
a list of increasing bit indices. Mostly to stay in sync with the `pred`

/ `succ`

functions below.

:: Int | size of the set we want. If larger than memo limit, will just call |

-> Vector Int |

Memoized version of `popCntSorted`

for `Int`

s.

NOTE Since this uses `popCntSorted`

for now it will still require a lot
of memory for sorting the vector!

:: Int | size of the set we want. If larger than memo limit, will just call |

-> Vector Word |

Memoized version of `popCntSorted`

for `Word`

s.

NOTE Since this uses `popCntSorted`

for now it will still require a lot
of memory for sorting the vector!

popShiftL :: Ranked t => t -> t -> t Source #

Move a population more to the left. This, effectively, introduces `0`

s
in the set, whereever the `mask`

has a `0`

. Only as many `1`

s can be
set, as the mask holds. Assume that you have a bitmask `mask = 10101`

and a least-significant aligned population `11`

, then given mask and
population you'd like to see `00101`

, i.e. the two lowest one bits of
the mask are set. `101`

would set the lowest and third one bit.

Examples:

`>>>`

5`popShiftL (21::Int) 3 -- 10101 00011 -- 00101`

`>>>`

0`popShiftL (28::Int) 0 -- 11100 00000 -- 00000`

`>>>`

4`popShiftL (28::Int) 1 -- 11100 00001 -- 00100`

`>>>`

8`popShiftL (28::Int) 2 -- 11100 00010 -- 01000`

`>>>`

12`popShiftL (28::Int) 3 -- 11100 00011 -- 01100`

popShiftR :: Ranked t => t -> t -> t Source #

Effectively compresses a bitset, given a mask. Removes set elements,
whenever the mask is `0`

, by moving all remaining elements one to the
right.

activeBitsL :: Ranked t => t -> [Int] Source #

List of all active bits, from lowest to highest.

activeBitsS :: (Ranked t, Monad m) => t -> Stream m Int Source #

A stream with the currently active bits, lowest to highest.

activeBitsV :: (Ranked t, Vector v Int) => t -> v Int Source #

A generic vector (specializes to the corrept type) of the active bits, lowest to highest.