Re: 'necklace'-type classes of combinatorial compositions

[john n <johnnagelson@yahoo.co.uk>]

Thanks very much for your amazingly quick help with this.

But your implementation lists some classes more than once. E.g:

? par_all(7,4)

[1, 1, 1, 4]
[1, 1, 2, 3]
[1, 1, 3, 2]
[1, 2, 1, 3]
[1, 2, 2, 2]

...but [1, 1, 2, 3] and [1, 1, 3, 2] are equivalent under a combination of
reflection and cycling.

Thanks again - I am very grateful!

Cheers,

John




Max A. wrote:
> 
> 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.
>>
>>
> 
>  
> 

-- 
View this message in context: http://www.nabble.com/%27necklace%27-type-classes-of-combinatorial-compositions-tf3895323.html#a11044329
Sent from the cr.yp.to - pari-users mailing list archive at Nabble.com.