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