Jérôme Raulin on Tue, 19 Jun 2018 23:33:23 +0200


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

forpart in multiplicity form


Dear all,

 

Would it be possible to add an option to forpart so that the partition are produced in multiplicity form, i.e. instead of having [1, 1, 1, 2, 2, 3] as one partition of 10 we would have the 3x2 matrix [1,3;2,2;3,1]. There is many places where it would be very useful.

Of course we can produce it manually from the standard output of forpart but there exist partitions generation algorithm directly working in multiplicity form for better performance.

From what I found the best one seems to be described in paper “A binary tree representations and related algorithms for generating integer partitions” by T. I. Fenner and G. Loizou (it is algorithm 5 on page 335).

As it is completely loop free it is very efficient (I implemented it in C++ and it is only 30% slower than the best known standard algorithm, AccelAsc in “Generating All Partitions: A Comparison of Two Encodings” by Jerome Kelleher; Barry O’Sullivan).

 

I don’t think that it could support the two options of forpart, maybe we could only use the fast algorithm when these options are not used and fall back to current one with multiplicity transformation when they are used.

I had a look at the source code of forpart_next in part.c and does not look like AccelAsc, maybe we could also implement it for the case when there is no restrictions on length and size for better performance.

 

Cheers

 

Jerome Raulin