Re: Enumeration of partitions

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Aug 01, 2024 at 04:49:03PM +0200, Emmanuel ROYER wrote:
> Dear Pari users!
> 
> There are two ways of representing a partition of an integer n, either as
> (a_1,...,a_q) where n=a_1+...+a_q
> or in the form
> (1^{b_1},...,n^{b_n}) with n=b_1+2b_2+...+nb_n. 
> 
> Unless I'm mistaken, partitions(n) returns the partitions in the first form.
> How can we translate the result into the second form as efficiently as
> possible? (Related to: how to count multiplicities in an ordered vector)

You can use matreduce!

? matreduce([1,1,1,1,3]))
%18 = [1,4;3,1]

> ? Partitions(57);
> cpu time = 30,995 ms, real time = 30,995 ms.
> ? Partitions3(57);
> cpu time = 38,106 ms, real time = 38,106 ms.

[matreduce(Vec(x)) | x <- partitions(57)];
  ***   last result computed in 495 ms.

Cheers,
Bill.