[GAP Forum] Forum Digest, Vol 166, Issue 2

[Kieran Roberts]

Hi Fatemeh,

You don't need to generate the partitions to determine the number of
ways to partition an n-set. GAP has a function called Bell(n) that
computes this number:

https://github.com/gap-system/gap/blob/master/lib/combinat.gi#L95-L105

that has complexity n^2.

Kieran.

> Message: 1
> Date: Mon, 18 Sep 2017 19:38:09 +0430
> From: fatemeh moftakhar <f.k.moftakhar at gmail.com>
> To: forum at gap-system.org
> Subject: [GAP Forum] Set Partitions
> Message-ID:
>         <CAOEkHNJy7xME+LZZU1C8upMHY_FU2MdTJ2RVF6TNLX5CtZEu8A at mail.gmail.com>
> Content-Type: text/plain; charset="UTF-8"
>
> Dear Colleagues,
>
> I need to the algorithm of computing the number of partitions of an n-set
> in GAP. Could you please send me the address of a paper or a book that
> contains such an algorithm?
> My main question is complexity of the algorithm that GAP uses for
> generating set partitions. I know the following paper that the complexity
> of this algorithm is \theta(1.6). Is this complexity  better than GAP
> algorithm?
>
> M. C. ER, A fast algorithm for generating set partitions, The Computer
> Journal, 31(3) (1988) 283-284.
>
> Best regards
> Fatemeh Moftakhar
>
>
> --
> Regards;
> Miss Fatemeh Moftakhar
> PhD Candidate,
> Department of Pure Mathematics,
> Faculty of Mathematical Sciences,
> University of Kashan, Kashan, Iran