Joerg Arndt on Wed, 05 Jun 2013 19:52:43 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: new GP loop: forpart() |
* Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr> [May 30. 2013 14:06]: > Dear PARI developers, > > I have commited a patch by Pascal and myself that adds GP function > to loop over partitions: > > forpart(v=5,print(v)) > Vecsmall([1,1,1,1,1]) > Vecsmall([1,1,1,2]) > Vecsmall([1,2,2]) > Vecsmall([1,1,3]) > Vecsmall([2,3]) > Vecsmall([1,4]) > Vecsmall([5]) > > [...] Firstly, a bug: forpart(p=0,print(p)) gives no output, it should give one empty vector. Secondly, I have now programmed a generator for the partitions (with bounds as in forpart()) represented as weakly decreasing lists: - the order is simply lex (this is often just the best choice) - largest part is (weakly) increasing, rendering bound on max part trivial. - zero case is handled correctly - decreasing lists are more convenient for some computations such as conjugate partition and hook length formulas Example: the 19 partitions of 11 with both bounds ==5 are generated as 1: [ 3 2 2 2 2 ] 2: [ 3 3 2 2 1 ] 3: [ 3 3 3 1 1 ] 4: [ 3 3 3 2 ] 5: [ 4 2 2 2 1 ] 6: [ 4 3 2 1 1 ] 7: [ 4 3 2 2 ] 8: [ 4 3 3 1 ] 9: [ 4 4 1 1 1 ] 10: [ 4 4 2 1 ] 11: [ 4 4 3 ] 12: [ 5 2 2 1 1 ] 13: [ 5 2 2 2 ] 14: [ 5 3 1 1 1 ] 15: [ 5 3 2 1 ] 16: [ 5 3 3 ] 17: [ 5 4 1 1 ] 18: [ 5 4 2 ] 19: [ 5 5 1 ] See http://jjj.de/fxt/demo/comb/#partition-desc-bb Speed: one update costs between 30 and 42 cycles, see timings at end of demo file in URL above. Note: I took bounds ==0 as "no bounds", this is trivial to change. Program passes valgrind in all corner cases I could find (caveat: no automation used). Todo (if wanted): backward iterator Is this really ever needed in practice? I have never needed one in any single case. Best regards, jj