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

Language | Haskell2010 |

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

Nibble !Word64 | |

Medium1 !Word64 | |

Medium2 !Word64 !Word64 | |

Medium3 !Word64 !Word64 !Word64 | |

Medium4 !Word64 !Word64 !Word64 !Word64 | |

WordList !Int ![Word64] |

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