| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Math.Combinat.Partitions.Integer.Compact
Contents
Description
Compact representation of integer partitions.
Partitions are conceptually nonincreasing sequences of positive integers.
When the partition fits into a 15x15 rectangle, we encode the parts as nibbles in a single 64-bit word. The most significant nibble is the first element, and the least significant nibble is used to encode the length. This way equality and comparison of 64-bit words is the same as the corresponding operations for partitions (lexicographic ordering).
This will make working with small partitions much more memory efficient (very helpful when building tables indexed by partitions, for example!) and hopefully quite a bit faster, too.
When they do not fit into a 15x15 rectangle, but fit into 255x7, 255x15, 255x23 or 255x31, respectively, then we extend the above to use the bytes of 1, 2, 3 or 4 64-bit words.
In the general case, we encode the partition as a list of 64-bit words, each encoding 4 16-bit parts.
Partitions with elements bigger than 65535 are not supported.
Note: This is an internal module, you are not supposed to import it directly.
Synopsis
- data Partition
- partitionPrefixChar :: Partition -> Char
- pattern Nil :: Partition
- pattern Cons :: Int -> Partition -> Partition
- pattern Partition_ :: [Int] -> Partition
- pattern Head :: Int -> Partition
- pattern Tail :: Partition -> Partition
- pattern Length :: Int -> Partition
- cmp :: Partition -> Partition -> Ordering
- empty :: Partition
- isEmpty :: Partition -> Bool
- singleton :: Int -> Partition
- uncons :: Partition -> Maybe (Int, Partition)
- partitionTail :: Partition -> Partition
- cons :: Int -> Partition -> Partition
- snoc :: Partition -> Int -> Partition
- toExponentialForm :: Partition -> [(Int, Int)]
- fromExponentialForm :: [(Int, Int)] -> Partition
- width :: Partition -> Int
- height :: Partition -> Int
- widthHeight :: Partition -> (Int, Int)
- diffSequence :: Partition -> [Int]
- reverseDiffSequence :: Partition -> [Int]
- c_dual_nibble :: Word64 -> Word64
- dualPartition :: Partition -> Partition
- toList :: Partition -> [Int]
- toDescList :: Partition -> [Int]
- toAscList :: Partition -> [Int]
- fromDescList :: [Int] -> Partition
- fromDescList' :: Int -> [Int] -> Partition
- makeNibble :: Int -> [Int] -> Partition
- makeMedium :: Int -> [Int] -> Partition
- makeMedium1 :: Int -> [Int] -> Partition
- makeMedium2 :: Int -> [Int] -> Partition
- makeMedium3 :: Int -> [Int] -> Partition
- makeMedium4 :: Int -> [Int] -> Partition
- makeWordList :: Int -> [Int] -> Partition
- isSubPartitionOf :: Partition -> Partition -> Bool
- dominates :: Partition -> Partition -> Bool
- pieriRuleSingleBox :: Partition -> [Partition]
- pieriRule :: Partition -> Int -> [Partition]
- i2w :: Int -> Word64
- w2i :: Word64 -> Int
- sum' :: [Word64] -> Word64
- safeTail :: [Int] -> [Int]
- toZero :: Int -> [Int]
- toOne :: Int -> [Int]
The compact partition data type
Constructors
| Nibble !Word64 | |
| Medium1 !Word64 | |
| Medium2 !Word64 !Word64 | |
| Medium3 !Word64 !Word64 !Word64 | |
| Medium4 !Word64 !Word64 !Word64 !Word64 | |
| WordList !Int ![Word64] |
Instances
| Eq Partition Source # | |
| Ord Partition Source # | |
Defined in Math.Combinat.Partitions.Integer.Compact | |
| Show Partition Source # | |
partitionPrefixChar :: Partition -> Char Source #
for debugging
Pattern synonyms
pattern Nil :: Partition Source #
Pattern sysnonyms allows us to use existing code with minimal modifications
pattern Partition_ :: [Int] -> Partition Source #
Simulated newtype constructor
Lexicographic comparison
Basic (de)constructrion
partitionTail :: Partition -> Partition Source #
partitionTail p == snd (uncons p)
snoc :: Partition -> Int -> Partition Source #
We assume that the element is not bigger than the last element!
exponential form
Width and height of the bounding rectangle
Differential sequence
diffSequence :: Partition -> [Int] Source #
From a non-increasing sequence [a1,a2,..,an] this computes the sequence of differences
[a1-a2,a2-a3,...,an-0]
reverseDiffSequence :: Partition -> [Int] Source #
From a non-increasing sequence [a1,a2,..,an] this computes the reversed sequence of differences
[ a[n]-0 , a[n-1]-a[n] , ... , a[2]-a[3] , a[1]-a[2] ]
Dual partition
c_dual_nibble :: Word64 -> Word64 Source #
dualPartition :: Partition -> Partition Source #
Conversion to list
toDescList :: Partition -> [Int] Source #
returns a descending (non-increasing) list
Conversion from list
fromDescList :: [Int] -> Partition Source #
We assume that the input is a non-increasing list of positive integers!
Partial orderings
Pieri rule
pieriRuleSingleBox :: Partition -> [Partition] Source #
Expands to product s[lambda]*h[1] = s[lambda]*e[1] as a sum of s[mu]-s. See https://en.wikipedia.org/wiki/Pieri's_formula
pieriRule :: Partition -> Int -> [Partition] Source #
Expands to product s[lambda]*h[k] as a sum of s[mu]-s. See https://en.wikipedia.org/wiki/Pieri's_formula