Max Alekseyev on Sun, 10 Jun 2007 00:00:32 +0200

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

Re: 'necklace'-type classes of combinatorial compositions

My quick-n-dirty implementation is attached.
Function par_all() iterates over the smallest lexicographical
representatives of each equivalence class and calls process() function
for every such representative. Currently process() simply prints out
its argument. E.g.:

? par_all(9,3)
[1, 1, 7]
[1, 2, 6]
[1, 6, 2]
[1, 3, 5]
[1, 5, 3]
[2, 2, 5]
[1, 4, 4]
[2, 3, 4]
[2, 4, 3]
[3, 3, 3]


On 6/9/07, john n <> wrote:

Hello, I am a PARI-GP newbie and wondered whether someone might help me with
code for listing the classes of combinatorial compositions of p which
contain q elements, and which are equivalent under reflection or cycling.
These are closely related to "necklaces".

Each equivalence class can be denoted by its lexicographically first
element, e.g. when p=10 and q=3,
{{1,2,6},{2,6,1},{6,1,2},{6,2,1},{2,1,6},{1,6,2}} can be denoted by {1,2,6}.

This is not the same as listing partitions because usually at least some
partitions containing the same elements are not equivalent to each other.

E.g. when p=10 and q=4, the compositions {1,2,2,5} cannot be transformed
into {2,1,2,5} by reflection, cycling, or both, because the instances of '2'
are adjacent in one and non-adjacent in the other.

A big thank you for any help with this!

John N

View this message in context:
Sent from the - pari-users mailing list archive at

Description: Binary data