Post #2735413
2026-05-11 14:01 UTC
@byorgey@mathstodon.xyz @oantolin@mathstodon.xyz @das_g@chaos.social Here's another go, I think getting to your desired running time of O(length p + maximum p). Start off by observing that it's an unfold:
```
conjugate :: [Int] -> [Int]
conjugate = unfoldr strip where
strip [] = Nothing
strip ns = Just (length ns, takeWhile (>0) [ n - 1 | n <- ns ])
```
This assumes that the input is a non-increasing list of positive naturals, and returns a result similarly.
Replies (1)
-
@jer_gib@functional.cafe 2026-05-11 14:01
@byorgey@mathstodon.xyz @oantolin@mathstodon.xyz @das_g@chaos.social This still takes time proportional to the sum of the partition, because we're only stripping off 1 at a time. You can improve that by stripping off `minimum ns` in one go: ``` conjugate :: [Int] -> [Int] conjugate [] = [] conjugate ns = replicate m (length ns) ++ conjugate (takeWhile (>0) [ n - m | n <- ns ]) where m = minimum ns ``` We are effectively snipping off the largest leftmost rectangle from the Ferrers diagram, rather than a single column. I would guess that this achieves the desired complexity.