Post #2735402
2026-05-10 22:08 UTC
Aha, I think it must have something to do with the bijection between encodings of integer partitions as (1) nonincreasing lists of natural numbers and (2) arbitrary lists of natural numbers, witnessed by sending a nondecreasing list to its list of successive differences. For example, the partition [6,6,4,3] corresponds to [0,2,1,3]. (6 - 6 = 0, 6 - 4 = 2, etc.)
I'm quite sure I have seen this bijection exploited before, perhaps in Richard Bird's book Pearls of Functional Algorithm Design? I'll have to look once I get back to my office tomorrow.
Replies (1)
-
@oantolin@mathstodon.xyz 2026-05-10 23:33
@byorgey@mathstodon.xyz oh, those succesive differences are the number of copies of 1, 2, 3,... in the conjugate. In your example there are 0 ones, 2 twos, 1 three, 3 fours. So something like (untested so probably slightly wrong): conjugate p = reverse . concat $ zipWith replicate (zipWithExt (-) 0 p (tail p)) [1..length p]