Joerg Arndt on Sat, 17 Jun 2006 12:15:49 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Partitions question


* McLaughlin, James <JMcLaughlin2@wcupa.edu> [Jun 17. 2006 11:25]:
> Is there a command in pari/gp that takes a positive integer and outputs a list
> of the un-restricted partitions?
>  
> Failing that, does anyone have an efficient piece of code already worked out?

See section 5.6.2 "Iterative algorithm", pp.169ff of the fxtbook
URL is http://www.jjj.de/fxt/#fxtbook

The code can be found on the same page (fxt package),
it generates about 140 million partitions per
second on a AMD64, 2.2GHz (16 CPU cycles per update)

You can find more combinatorial algorithms in chapter 5, pp.155ff
Some of the implementations might be useful for inclusion
in pari/gp (e.g. a Gray code for permutations that needs less than
10 CPU cycles per update).

I'd appreciate any feedback on both the fxtbook and the code.