Showing posts with label Haskell. Show all posts
Showing posts with label Haskell. Show all posts
29 October 2007
Enumerating multiset partitions
Brent Yorgey on enumerating multiset partitions. He came to the problem the same way I did -- I was trying to count the number of factorizations of an integer. An integer of the form pn, where p is a prime, has p(n) factorizations, where p(n) is the partition function; for example
giving the p(5) = 7 factorizations of p5. An integer of the form p1p2...pn has Bn factorizations (the nth Bell number); for example, 2310 = (2)(3)(5)(7)(11) has fifty-two factorizations. But what about, say, an integer of the form p3qr? How many factorizations does it have? Naturally, this associates an integer with each partition; from the number p5 we get the partition 5 and the number of factorizations 15; from the number p1p2p3p4p5 we get the partition 1 + 1 + 1 + 1 + 1 we associate 52.
Unfortunately, I don't really follow Yorgey's work because I don't know Haskell. And I don't know a general way to compute these yet, except in the trivial cases. But, for example, p2 q has four factorizations:
(p2q) = (p2)(q) = (p)(pq) = (p)(p)(q)
and so we associate to 2 + 1 the number 4; this is intermediate between p(3) (which is 3) and B3 (which is 5). This makes sense; in general p(n) counts the number of partitions of {1, ..., n} when no elements are distinguishable, and Bn when all elements are distinguishable. Multiset partitions interpolate between integer partitions and set partitions.
(Yorgey says that the problem is also solved in Volume 4, Fascicle 3 of Knuth, which I may track down. But I want the pleasure of working this out for myself, to some extent.)
Yorgey also says that he found the problem via Project Euler, which gives a couple hundred examples of problems that can, in general, be solved by ridiculously inefficient brute force methods or by elegant methods that require not so much computation.
p^5 = p^4 p = p^3 p^2 = p^3 p p = p^2 p^2 p = p^2 p p p = p p p p p
giving the p(5) = 7 factorizations of p5. An integer of the form p1p2...pn has Bn factorizations (the nth Bell number); for example, 2310 = (2)(3)(5)(7)(11) has fifty-two factorizations. But what about, say, an integer of the form p3qr? How many factorizations does it have? Naturally, this associates an integer with each partition; from the number p5 we get the partition 5 and the number of factorizations 15; from the number p1p2p3p4p5 we get the partition 1 + 1 + 1 + 1 + 1 we associate 52.
Unfortunately, I don't really follow Yorgey's work because I don't know Haskell. And I don't know a general way to compute these yet, except in the trivial cases. But, for example, p2 q has four factorizations:
(p2q) = (p2)(q) = (p)(pq) = (p)(p)(q)
and so we associate to 2 + 1 the number 4; this is intermediate between p(3) (which is 3) and B3 (which is 5). This makes sense; in general p(n) counts the number of partitions of {1, ..., n} when no elements are distinguishable, and Bn when all elements are distinguishable. Multiset partitions interpolate between integer partitions and set partitions.
(Yorgey says that the problem is also solved in Volume 4, Fascicle 3 of Knuth, which I may track down. But I want the pleasure of working this out for myself, to some extent.)
Yorgey also says that he found the problem via Project Euler, which gives a couple hundred examples of problems that can, in general, be solved by ridiculously inefficient brute force methods or by elegant methods that require not so much computation.
Subscribe to:
Comments (Atom)