Max Alekseyev on Mon, 02 Jul 2007 22:29:52 +0200


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

Re: 'necklace'-type classes of combinatorial compositions


John,

Simply replace the line

     if(lex(u,vector(l,k,u[(j+k-2)%l + 1]))==1 ||
lex(u,vector(l,k,u[(j-k)%l + 1]))==1, g=0; break);

with

     if(lex(u,vector(l,k,u[(j+k-2)%l + 1]))==1, g=0; break);

That is, out of two conditions connected with OR operator ("||"), you
need only the first one (corresponding to pure rotations).

Regards,
Max

On 7/2/07, john n <johnnagelson@yahoo.co.uk> wrote:

Thank you again for your very kind help with this. Your code has been
tremendously useful.

If I might 'pick your brains' again (!), I wondered whether you might show
me how to amend it, so that classes are defined as containing elements that
are equivalent under rotation, but not under reflection or a combination of
both,

E.g. among the compositions yielded by

function(18,5)

would be both [1,5,3,2,7] and [1,7,2,3,5] because one cannot be transformed
into the other by rotation.

Thanks again,

John


Max A. wrote:
>
> Yeah, sorry about this bug.
> Hopefully, the attached version has no bugs.
>
> Regards,
> Max
>
> On 6/9/07, john n <johnnagelson@yahoo.co.uk> wrote:
>>
>> 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.
>>
>>
>
>
>

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