Re: 'necklace'-type classes of combinatorial compositions

["Max Alekseyev" <maxale@gmail.com>]

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]

Regards,
Max

On 6/9/07, john n <johnnagelson@yahoo.co.uk> 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: http://www.nabble.com/%27necklace%27-type-classes-of-combinatorial-compositions-tf3895323.html#a11043232
> Sent from the cr.yp.to - pari-users mailing list archive at Nabble.com.

Attachment: part2.gp
Description: Binary data