Re: Enumeration of partitions

[Emmanuel ROYER <emmanuel.royer@uca.fr>]

Thank you very much Bill and Denis for your answers!
If a really need the representation with all the zeroes, then I use both of your method

Partitions(n)={
  apply( p->
    my( v = Vecsmall(0,n));
    for( j = 1, matsize(p)[1], v[p[j,1]]=p[j,2]);
    v
  , [matreduce(Vec(pa)) | pa<-partitions(n)]
  );
};

But, the time cost is so great that I had a second thought on the way I use the representations to use Bill representations of the partitions. 

I forgot matreduce had already appear a few time ago, this is a great command even though I cannot remember its name!

Emmanuel Royer
Professeur à l'Université Clermont Auvergne
https://royer.perso.math.cnrs.fr
----
Institut CNRS-Pauli
IRL2842
CNRS & Wolfgang Pauli Institut

----- Mail original -----
De: "Denis Simon" <denis.simon@unicaen.fr>
À: "pari-users" <pari-users@pari.math.u-bordeaux.fr>
Envoyé: Jeudi 1 Août 2024 17:46:55
Objet: Re: Enumeration of partitions

Here is an improvement of my previous script, based on apply(), which can easily be replaced by parapply().
But still not competitive with Bill's solution...

Partitions6(n)=
{
  apply( p->
    my( v = Vecsmall(0,n));
    for( j = 1, #p, v[p[j]]++);
    v
  , partitions(n)
  );
}

Denis SIMON.

----- Mail original -----
> De: "Denis Simon" <denis.simon@unicaen.fr>
> À: "pari-users" <pari-users@pari.math.u-bordeaux.fr>
> Envoyé: Jeudi 1 Août 2024 17:16:00
> Objet: Re: Enumeration of partitions

> If you want the output to contain lots of 0, you can try the following function.
> However, it does not return exactly the same as your functions, so I am possibly
> mistaking somewhere...
> 
> Denis SIMON.
> 
> Partitions4(n)=
> {
>  my(P=partitions(n));
>  my(Part = vector(#P,i,Vecsmall(0,n)));
>  for( i = 1, #P,
>    p = P[i];
>    for( j = 1, #p,
>      k = p[j];
>      Part[i][k]++
>    )
>  );
>  return(Part);
> }
> 
> 
> ----- Mail original -----
>> De: "Bill Allombert" <Bill.Allombert@math.u-bordeaux.fr>
>> À: "pari-users" <pari-users@pari.math.u-bordeaux.fr>
>> Envoyé: Jeudi 1 Août 2024 17:06:30
>> Objet: Re: Enumeration of partitions
> 
>> 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.