Safe Haskell	Safe-Inferred
Language	Haskell2010

Math.BitSet

Description

Bit set tricks (not so much).

Synopsis

msbOf :: Int -> Int
lsbOf :: Int -> Int
bitsOf :: Int -> Vector Int
log2 :: FiniteBits b => b -> Int
bitCeil :: Int -> Int
ceil2 :: Int -> Int
powersetM_ :: (Bits a, Num a, Monad m) => a -> (a -> m ()) -> m ()
powerset :: (Bits a, Num a) => a -> [a]
powersetU :: (Bits a, Num a, Unbox a) => a -> Vector a
unBitSet :: Int -> Int -> Vector Int
partitionsOf :: Int -> [[Int]]
partitionsOfK :: Int -> Int -> [[Int]]

Documentation

msbOf :: Int -> Int #

\(O(1)\) Retrieves the most significant bit.

>>> msbOf 0
-1
>>> msbOf maxBound
62
>>> msbOf $ 4 + 2 + 1
2

lsbOf :: Int -> Int #

\(O(1)\) Retrieves the least significant bit.

>>> lsbOf 0
-1
>>> lsbOf maxBound
0
>>> lsbOf $ 4 + 2 + 1
0

bitsOf :: Int -> Vector Int #

\(O(1)\)

log2 :: FiniteBits b => b -> Int #

\(O(1)\) Log base of two, floored. https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-Bits.html#v:countLeadingZeros

>>> log2 (0b11 :: Int)
1
>>> log2 (0b111 :: Int)
2

bitCeil :: Int -> Int #

\(O(1)\) Ceiling of log base 2 of an Int.

>>> bitCeil (0b11 :: Int)
2
>>> bitCeil (0b111 :: Int)
3

ceil2 :: Int -> Int #

\(O(1)\) Calculates the smallest integral power of two that is not smaller than x.

>>> ceil2 3
4

powersetM_ :: (Bits a, Num a, Monad m) => a -> (a -> m ()) -> m () #

\(O(2^N)\) Originally by @yamate11

powerset :: (Bits a, Num a) => a -> [a] #

\(O(2^N)\) Originally by @yamate11

>>> powerset (7 :: Int)
[7,6,5,4,3,2,1,0]

powersetU :: (Bits a, Num a, Unbox a) => a -> Vector a #

\(O(2^N)\) Returns a powerset of x0 in descending order.

>>> powersetU (7 :: Int)
[7,6,5,4,3,2,1,0]

unBitSet :: Int -> Int -> Vector Int #

\(O(W)\)

>>> unBitSet 4 5
[0,2]

TODO: which is faster: unfoldrExactN with count leading zeros.

partitionsOf :: Int -> [[Int]] #

\(O(N \cdot N!)\) DFS that enumerates all possible partitions of a bitset. Prefer partitionsOfK when you only need specific size of families.

>>> partitionsOf (bit 4 - 1)
[[8,4,2,1],[12,2,1],[8,6,1],[4,10,1],[14,1],[8,4,3],[12,3],[8,2,5],[10,5],[8,7],[4,2,9],[6,9],[4,11],[2,13],[15]]

partitionsOfK :: Int -> Int -> [[Int]] #

\(O(N \cdot N!)\) (or faster?) DFS that numerates partitions of size k0.

Typical problems

ABC 310 D - Peaceful Teams
ABC 319 D - General Weighted Max Matching (Not the exact pattern though)
Typical 045 - Simple Grouping (★ 6)

DP

Faster solution would be \(O(2^N N)\) (correct?) DP. Use pushBasedConstructN ((0, 0), (bit n - 1, n)) or fold-like times k for that. Choose sets with the lsb of the remaining set only.