permutation groups for cube and dodecahedron?

[smichr]

In a docstring the permutation group for the tetrahedron is given. I would like to inlclude the same for the cube and dodecahedron (and hence their doubles, octahedron and icosahedron). I've googled a bit without finding the explicit form that I need. This is outside my field and perhaps someone else is a little more savvy at coming up with this? I need something like this which is defined for the tetrahedron:

[Permutation([[0,1,2], [3]]),\

Permutation([[0,1,3], [2]]),\

Permutation([[0,2,3], [1]]),\

Permutation([[1,2,3], [0]]),\

Permutation([[0,1], [2,3]]),\

Permutation([[0,2], [1,3]]),\

Permutation([[0,3], [1,2]]),\

Permutation([0,1,2,3])]

Any help would be appreciated.

[David Joyner]

On Mon, Aug 20, 2012 at 8:20 PM, smichr <smi...@gmail.com> wrote:
> In a docstring the permutation group for the tetrahedron is given. I would
> like to inlclude the same for the cube and dodecahedron (and hence their
> doubles, octahedron and icosahedron). I've googled a bit without finding the
> explicit form that I need. This is outside my field and perhaps someone else

The cube has 8 vertices, so the permutation group representation
of the symmetry group of the cube is a copy of S_4 sitting inside S_8 in a
particular way.

The dodecahedron has 20 vertices, so the permutation group representation
of the symmetry group of the dodecahedron is a copy of A_5 sitting
inside S_{20} in a
particular way.

It's not pretty.

If you really want these, I would just take two randomish symmetries,
compute their
permutations by labeling a cube/dodecahedron's vertices in some way, and then
computing the group generated by just those two. My bet is that will
be the whole thing.
It's a bit messy. I did stuff like that in my book Adventures in Group Theory
(and there is a free but very errata-filled copy on the web at
http://www.permutationpuzzles.org/rubik/webnotes/).

> is a little more savvy at coming up with this? I need something like this
> which is defined for the tetrahedron:
>
> [Permutation([[0,1,2], [3]]),\
> Permutation([[0,1,3], [2]]),\
> Permutation([[0,2,3], [1]]),\
> Permutation([[1,2,3], [0]]),\
> Permutation([[0,1], [2,3]]),\
> Permutation([[0,2], [1,3]]),\
> Permutation([[0,3], [1,2]]),\
> Permutation([0,1,2,3])]
>
> Any help would be appreciated.
>

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/sympy/-/8qIa6K5wjc0J.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to
> sympy+un...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/sympy?hl=en.

[Chris Smith]

On Tue, Aug 21, 2012 at 6:49 AM, David Joyner <wdjo...@gmail.com> wrote:
> On Mon, Aug 20, 2012 at 8:20 PM, smichr <smi...@gmail.com> wrote:
>> In a docstring the permutation group for the tetrahedron is given. I would
>> like to inlclude the same for the cube and dodecahedron (and hence their
>> doubles, octahedron and icosahedron). I've googled a bit without finding the
>> explicit form that I need. This is outside my field and perhaps someone else
>
> The cube has 8 vertices, so the permutation group representation
> of the symmetry group of the cube is a copy of S_4 sitting inside S_8 in a
> particular way.
>
> The dodecahedron has 20 vertices, so the permutation group representation
> of the symmetry group of the dodecahedron is a copy of A_5 sitting
> inside S_{20} in a
> particular way.
>
> It's not pretty.
>
> If you really want these, I would just take two randomish symmetries,
> compute their
> permutations by labeling a cube/dodecahedron's vertices in some way, and then
> computing the group generated by just those two. My bet is that will
> be the whole thing.

OK, I've convinced myself that all permutations can be generated from
two fixed axes of rotation -- the axes stay fixed as the polyhedron
moves. What is special about the "group"? Is it that all the
permutations can be generated with only powers of those permutations,
not from mixtures of the same? So it's a bit like a group of prime
factors (the two axes) as opposed to general divisors (members of the
group that just get applied once).

/c

[David Joyner]

Let a, b be your two elements determined by rotation.
Is this your question?
Q: Does the group have the property that every element has the form
a^mb^n, for some m,n?

I don't know. What I am saying is that I am willing to believe (because it is
very very often true for most permutation groups) that all elements
of G can be written in the form a^m1*b^n1*a^m2*b^n2*...*a^mk*b^nk,
for some m1, ..., mk, n1, ..., nk. You'd have to check this using
Sage or Gap or, now Sympy. ( I'm not sure if Aleksander ever
finished correctly implementing the disjoint cycle notation. If not, Sage
or Gap would probably be easist.) You enter a, b as generators of the
group, compute
its order and see if the order if what you think it should be (60 for
A_5, for example).

Incidently, Jesse Douglas, who solved Plateau's problem (a problem
in differential geometry which arose in the study of how soap film
forms a minimal
surface when the boundary is some closed wire loop) and got one of
the two first Fields Medals for his work, turned to researching finite
groups as he got older. He apparently classified the finite groups
which do have the property mentioned in your question above.
I think they are all published in the PNAS and on the web, but I have not read
them. So, I think the answer to your question might follow from what
is known theoretically from Douglas' work. I'll try to look up those papers
as soon as I get the time and let you know.

> factors (the two axes) as opposed to general divisors (members of the
> group that just get applied once).
>
> /c
>

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.

[Chris Smith]

> I don't know. What I am saying is that I am willing to believe (because it is
> very very often true for most permutation groups) that all elements
> of G can be written in the form a^m1*b^n1*a^m2*b^n2*...*a^mk*b^nk,
> for some m1, ..., mk, n1, ..., nk.

Yes, that's what I see. So to generate the 31 permutations for the
dodecahedron I define a top face rotation, f0, and a front face
rotation, f1, and then, for example, face 2 rotation is equivalent to
doing f0*f1*f0**4.

> Sage or Gap or, now Sympy. ( I'm not sure if Aleksander ever
> finished correctly implementing the disjoint cycle notation. If not, Sage
> or Gap would probably be easist.)

Do you mean cyclic notation, like ((123)(465)) ?

We have that, but I think it uses the unconventional R to L rather
than L to R convention:

>>> p=Permutation
>>> p([[1,2],[0],[3]])*p([[2,3],[0],[1]]
... )
Permutation([0, 2, 3, 1])
>>> _.cyclic_form
[[1, 2, 3], [0]]


http://en.wikipedia.org/wiki/Cycle_notation says that the answer of
the above should be (132) not (123) (which is what SymPy gives when
the order of multiplication is reversed).

> Incidently, Jesse Douglas, who solved Plateau's problem (a problem
> in differential geometry which arose in the study of how soap film
> forms a minimal
> surface when the boundary is some closed wire loop) and got one of
> the two first Fields Medals for his work, turned to researching finite
> groups as he got older. He apparently classified the finite groups
> which do have the property mentioned in your question above.
> I think they are all published in the PNAS and on the web, but I have not read
> them. So, I think the answer to your question might follow from what
> is known theoretically from Douglas' work. I'll try to look up those papers
> as soon as I get the time and let you know.

If it's easy to put your hands on it, thanks.

[Chris Smith]

With the aid of a manipulable dodecahedron I was able to construct the
permutation group. All pgroups of the polyhedra are now included in
Polyhedron. Thanks for the encouragement.

I added a lot to the documentation with hopes of it being useful to
someone that is about as initiated as I was at the beginning of the
work on Saptarshi's combinatorics branch.

Would you have any time to look over the changes that have been made
at https://github.com/sympy/sympy/pull/1508?

[David Joyner]

To start, it is great that you are implementing this. Very interesting code
and useful and very tedious to work out, so *thanks very much" for that.

I only looked at the diff, and haven't tried downloading and running
your patch yet.
A few comments.

First, you say

" Although only 2 permutations are needed for a polyhedron in order to
generate all the possible orientations, it is customary to give a
group of permutations (P0, P1, ...) such that powers of them alone are
able to generate the orientations, e.g. P0, P0**2, P0**3, P1, P1**2,
etc..., instead of mixed permutations (P0*P1**2*P0). The following
work was used to calculate the permutation group of the polyhedra."

What does this mean? Why is it customary to give a "group" (you
mean "set" or "collection" I guess?) of perms s.t. powers alone generate
the "orientations" (I guess you mean "group elements" I guess?)?
I don't understand what this means.

I was also confused at first what "0-based" and "1-based" cycle notation
meant. I figured it out (or think I did) from the context and your examples,
but others might find it confusing. Just FYI.

Second, you say you give tests but no where do I see you say

"the permutation group representation of the symmetry group

of the cube is isomorphic to S_4" and test that the group you
generate has 24 elements. Am I missing something?
Similarly, I did not see "the permutation group representation
of the symmetry group of the dodecahedron is isomrphic to A_5"
and test that it has 60 elements.
If you don't do this, I don't see how you can be sure it is correct.

[David Joyner]

On Thu, Aug 23, 2012 at 11:16 AM, Chris Smith <smi...@gmail.com> wrote:
>> I don't know. What I am saying is that I am willing to believe (because it is
>> very very often true for most permutation groups) that all elements
>> of G can be written in the form a^m1*b^n1*a^m2*b^n2*...*a^mk*b^nk,
>> for some m1, ..., mk, n1, ..., nk.
>
> Yes, that's what I see. So to generate the 31 permutations for the
> dodecahedron I define a top face rotation, f0, and a front face
> rotation, f1, and then, for example, face 2 rotation is equivalent to
> doing f0*f1*f0**4.
>
>> Sage or Gap or, now Sympy. ( I'm not sure if Aleksander ever
>> finished correctly implementing the disjoint cycle notation. If not, Sage
>> or Gap would probably be easist.)
>
> Do you mean cyclic notation, like ((123)(465)) ?

Yes.

>
> We have that, but I think it uses the unconventional R to L rather
> than L to R convention:
>
>>>> p=Permutation
>>>> p([[1,2],[0],[3]])*p([[2,3],[0],[1]]
> ... )
> Permutation([0, 2, 3, 1])
>>>> _.cyclic_form
> [[1, 2, 3], [0]]
>
>
> http://en.wikipedia.org/wiki/Cycle_notation says that the answer of
> the above should be (132) not (123) (which is what SymPy gives when
> the order of multiplication is reversed).
>

Actually, that is very bad I think. If it doesn't follow standard
conventions and notations,
people will not use it.


>

...

>> them. So, I think the answer to your question might follow from what
>> is known theoretically from Douglas' work. I'll try to look up those papers
>> as soon as I get the time and let you know.
>
> If it's easy to put your hands on it, thanks.
>

I looked at them today. Sorry, but it is much more complicated than I thought.
In fact, I don't think I can answer your question using Douglas' results.
Sounds like you don't really need his results anyway, so I guess it isn't
a big deal.

[Chris Smith]

>> We have that, but I think it uses the unconventional R to L rather
>> than L to R convention:
>>
>>>>>
p=Permutation
>>>>> p([[1,2],[0],[3]])*p([[2,3],[0],[1]]
>> ... )
>> Permutation([0, 2, 3, 1])
>>>>> _.cyclic_form
>> [[1, 2, 3], [0]]
>>
>>
>> http://en.wikipedia.org/wiki/Cycle_notation says that the answer of
>> the above should be (132) not (123) (which is what SymPy gives when
>> the order of multiplication is reversed).
>>
>
> Actually, that is very bad I think. If it doesn't follow standard
> conventions and notations,
> people will not use it.

I've got this fixed but there are lots of failures in other areas of
combinatorics so i might as well close this for now. I (as you)
consider this a show stopper.

[Chris Smith]

> " Although only 2 permutations are needed for a polyhedron in order to
> generate all the possible orientations, it is customary to give a
> group of permutations (P0, P1, ...) such that powers of them alone are
> able to generate the orientations, e.g. P0, P0**2, P0**3, P1, P1**2,
> etc..., instead of mixed permutations (P0*P1**2*P0). The following
> work was used to calculate the permutation group of the polyhedra."
>
> What does this mean? Why is it customary to give a "group" (you
> mean "set" or "collection" I guess?) of perms s.t. powers alone generate
> the "orientations" (I guess you mean "group elements" I guess?)?
> I don't understand what this means.

One can supply a "pgroup" to Polyhedron so I was using the word
"group" for that purpose. I'm open to a new way of saying this. For a
cube you could generate all permutations with two permutations: one
that corresponds to rotating cw from the top and one that corresponds
to rotating cw from the front face. But there are 3 face, 6 edge and 4
vertex permutation groups that can be defined, too. Multiple
applications of just the top and front face will not show you all
orientations of the cube -- they can only show you 6 of the 24 --
whereas application of the others will show all the orientations. I
don't know how best to say this.

>
> I was also confused at first what "0-based" and "1-based" cycle notation
> meant. I figured it out (or think I did) from the context and your examples,
> but others might find it confusing. Just FYI.

I think a way around this is to always add 0 to permutations that
don't have a 0 and just let the user ignore that 0. That way they can
give permutations with or without the zero and those functions for
dealing with one or the other can be removed.

>
> Second, you say you give tests but no where do I see you say
> "the permutation group representation of the symmetry group
> of the cube is isomorphic to S_4" and test that the group you
> generate has 24 elements. Am I missing something?

The check() function in test_polyhedron does this. For each type of
polyhedra it checks that 24 different orientations are generated. It
also makes sure that each permutation given cycle back to the original
within the allowed number of applications.

> Similarly, I did not see "the permutation group representation
> of the symmetry group of the dodecahedron is isomrphic to A_5"
> and test that it has 60 elements.
> If you don't do this, I don't see how you can be sure it is correct.

I sweated over this for a couple of days...and got it wrong several
times! :-) I think the test is correct but it would help if you took a
look to see if it's convincing to you. Also, if there is a more
correct way of saying something, please just annotate the code in
github and I can see exactly the line you are referring to and can
make the change.

Thanks for looking this over. I'll keep working out the kinks related
to multiplication order.

/c

[Tom Bachmann]

Huh? At least in my courses, cycles where just a short-hand notation for
permutations, and where composed in precisely the way this code does. I
know there are arguments for composing on the right, but I don't think
this is universally done (or even by a majority). I don't know about
specialised fields, though (e.g. there is a famous crystallography book
composing on the right, but even in its field it is an exception, not
the rule).

[Chris Smith]

It's as it was, using L to R but I added a reverse option so one can
go R to L if desired.

[David Joyner]

Can you please explain, in terms a complete idiot like me can understand,
what steps I go through to test your code? I have access to macs
(running lion) and linux (running ubuntu 12.04), both with git installed.
Someone told me once with Aleksander M's branches but I've forgotten the
steps and am not sure how well the instructions translate to your patches.

[Chris Smith]

>
> Can you please explain, in terms a complete idiot like me can understand,
> what steps I go through to test your code? I have access to macs
> (running lion) and linux (running ubuntu 12.04), both with git installed.
> Someone told me once with Aleksander M's branches but I've forgotten the
> steps and am not sure how well the instructions translate to your patches.
>

ok, so you have a sympy repo already? If so, then

git add remote smichr git...@github.com/smichr/sympy.git
git pull smichr
git checkout smichr/combinatorics

You could also just try the sympy-bot but I hadn't got that to work.
There may be more efficient ways to do what I suggest above, but
that's what I do when I want to test someone's work.

/c

[David Joyner]

On Sat, Aug 25, 2012 at 10:21 AM, Chris Smith <smi...@gmail.com> wrote:
>>
>> Can you please explain, in terms a complete idiot like me can understand,
>> what steps I go through to test your code? I have access to macs
>> (running lion) and linux (running ubuntu 12.04), both with git installed.
>> Someone told me once with Aleksander M's branches but I've forgotten the
>> steps and am not sure how well the instructions translate to your patches.
>>
> ok, so you have a sympy repo already? If so, then
>
> git add remote smichr git...@github.com/smichr/sympy.git
> git pull smichr
> git checkout smichr/combinatorics
>

Should this work?

git clone git://github.com/sympy/sympy.git
cd sympy

git add remote smichr git...@github.com/smichr/sympy.git
git pull smichr
git checkout smichr/combinatorics

If so, it doesn't work for me. For example, the third line gives

she:sympy davidjoyner$ git add remote smichr git...@github.com/smichr/sympy.git
fatal: pathspec 'remote' did not match any files

> You could also just try the sympy-bot but I hadn't got that to work.
> There may be more efficient ways to do what I suggest above, but
> that's what I do when I want to test someone's work.
>
> /c
>

[Chris Smith]

>> git add remote smichr git...@github.com/smichr/sympy.git

Sorry. Make that git remote add smichr git...@github.com/smichr/sympy.git

[David Joyner]

On Sat, Aug 25, 2012 at 10:56 AM, Chris Smith <smi...@gmail.com> wrote:
>>> git add remote smichr git...@github.com/smichr/sympy.git
>
>
> Sorry. Make that git remote add smichr git...@github.com/smichr/sympy.git

git clone git://github.com/sympy/sympy.git
cd sympy

git remote add smichr git...@github.com/smichr/sympy.git

git pull smichr

returns

fatal: 'git...@github.com/smichr/sympy.git' does not appear to be a
git repository
fatal: The remote end hung up unexpectedly

[Aaron Meurer]

A few things here:

- As git correctly points out, git...@github.com/smichr/sympy.git is
not a valid URL. A more correct URL is
g...@githib.com:smichr/sympy.git, but that is also incorrect in this
situation because that is Chris's private ssh URL, which only he can
use. What you should do is go to https://github.com/smichr/sympy and
copy the clone URL. Either HTTP or Git read-only will do. In this
case, you get https://github.com/smichr/sympy. Then the command is git
remote add smichr https://github.com/smichr/sympy

- You don't need to clone SymPy again (ever). Just cd into the clone
you already have and run the commands there.

- While it will work, git fetch smichr is better than git pull smichr
to download changes from a remote.

Aaron Meurer

[Chris Smith]

> git clone git://github.com/sympy/sympy.git
> cd sympy
> git remote add smichr git...@github.com/smichr/sympy.git

slap forehead: a colon

git remote add smichr git...@github.com:smichr/sympy.git

[David Joyner]

On Sat, Aug 25, 2012 at 1:11 PM, Aaron Meurer <asme...@gmail.com> wrote:
> A few things here:
>
> - As git correctly points out, git...@github.com/smichr/sympy.git is
> not a valid URL. A more correct URL is
> g...@githib.com:smichr/sympy.git, but that is also incorrect in this
> situation because that is Chris's private ssh URL, which only he can
> use. What you should do is go to https://github.com/smichr/sympy and
> copy the clone URL. Either HTTP or Git read-only will do. In this
> case, you get https://github.com/smichr/sympy. Then the command is git
> remote add smichr https://github.com/smichr/sympy
>
> - You don't need to clone SymPy again (ever). Just cd into the clone
> you already have and run the commands there.
>
> - While it will work, git fetch smichr is better than git pull smichr
> to download changes from a remote.

Thanks! This worked:

git clone git://github.com/sympy/sympy.git
cd sympy

git remote add smichr https://github.com/smichr/sympy
git fetch smichr
git checkout smichr/combinatorics

[David Joyner]

Somehow, after doing all I say in my last email, I am not getting all
your functions.

>>> from sympy.combinatorics.permutations import *
>>> p = Permutation
>>> g = p([[2,3],[0],[1]])
>>> g.reduced_cyclic_form
[[2, 3]]
>>> full_cyclic_form0([[2,3]], 4)
Traceback (most recent call last):
File "<console>", line 1, in <module>
NameError: name 'full_cyclic_form0' is not defined

I see this function in this patch:
https://github.com/smichr/sympy/commit/b86464d8bf5acddd91d2623492a33e5c42d4d953
Can you explain what is going on here? I am gittng something wrong I think.

[Chris Smith]

I got rid of the `full_cyclic_form0` function. A zero will
automatically be added (and basically ignored) if you don't use it.

[Chris Smith]

I just updated the branch; you should be able to repull and have the
changes updated there. Nothing too major, though.

btw, I'm not sure if adding the 0 is a good way to go or not. I'm
trying to make it as compatible as possible for the person sitting
down to use this who is already familiar with combinatorics.

[David Joyner]

On Thu, Aug 23, 2012 at 11:16 AM, Chris Smith <smi...@gmail.com> wrote:

...

>
> Do you mean cyclic notation, like ((123)(465)) ?
>
> We have that, but I think it uses the unconventional R to L rather
> than L to R convention:
>
>>>> p=Permutation
>>>> p([[1,2],[0],[3]])*p([[2,3],[0],[1]]
> ... )
> Permutation([0, 2, 3, 1])
>>>> _.cyclic_form
> [[1, 2, 3], [0]]
>
>
> http://en.wikipedia.org/wiki/Cycle_notation says that the answer of
> the above should be (132) not (123) (which is what SymPy gives when
> the order of multiplication is reversed).
>

I confirmed that your code does as you said. Note that Gap does it
correctly:

gap> (1,2)*(2,3);
(1,3,2)

And even if you don't agree that this is "the correct" way to multiply
permutations,
the fact that Gap does it this way should I hope strongly suggest that
it is at least
the best way to do it.

The issue is this: there are several program used for group theory computations
by most people Gap, Magma, and Sage. (Maybe I should include Mathematica?
I don't know any serious group theory researchers who use it but maybe there are
some?) While Sage includes Gap, Sage has its own permutation multiplication
(implemented in cython). These three main programs have the following in common:

(1) they all use the usual disjoint cycle notation (without
singletons!) by default,
(2) they all multiply in exactly the same way.

It will be hard to switch people away from that. In fact, today I
asked a group-theorist
friend if he would use a group-theory program which does not use the usual
disjoint cycle notation and he said no.

What Aleksander did was great. The algorithms can be very hard to
understand correctly.
There is a lot of good functionality now. That is definitely the hard part.

I hope this interface issue is not too hard to correct.

>

...

[Chris Smith]

Well, one way to "fix" it would be to overload __pow__ so that P**int
does the usual power but P**P does multiplication...but python will
parse this from R to L. Does P**P have meaning of its own?

[Aaron Meurer]

I wonder if you could ask your colleagues how they feel about using a
zero-based system instead of a one-based one (i.e., in this context,
Sn = {0, 1, 2, ..., n - 1} instead of {1, 2, ..., n}). Because this is
once instance where it's usually better to stick with Python
conventions over math conventions.

Personally, I'm somewhat skeptical that it will "just work" to say,
"if you want to use a one-based system, just use Sn+1 and pretend the
first element isn't there".

Aaron Meurer

[David Joyner]

On Sun, Aug 26, 2012 at 1:43 AM, Aaron Meurer <asme...@gmail.com> wrote:
> On Sat, Aug 25, 2012 at 2:22 PM, David Joyner <wdjo...@gmail.com> wrote:
>> On Thu, Aug 23, 2012 at 11:16 AM, Chris Smith <smi...@gmail.com> wrote:
>>

...

>

> I wonder if you could ask your colleagues how they feel about using a
> zero-based system instead of a one-based one (i.e., in this context,
> Sn = {0, 1, 2, ..., n - 1} instead of {1, 2, ..., n}). Because this is
> once instance where it's usually better to stick with Python
> conventions over math conventions.

I don't think that is a big problem, as long as it is made clear in
the docs that
everything is 0 based, following normal Python conventions.

[David Joyner]

In group theory, (and in Gap) x^y means "conjugation" : y^(-1)*x*y.
This is not implemented in Sage, so I would not say it is universal.
It sounds like you are suggesting this: for elements of the Permutation
class:
1. define __mult__ to be L to R mult,
1. overload __pow__ to be R to L mult, if both args are perms, and
to be the usual power if the right arg is an int.
If that is what you are saying, then I vote +1 for it (provided
it is clearly documented as usual).

[Chris Smith]

> In group theory, (and in Gap) x^y means "conjugation" : y^(-1)*x*y.
> This is not implemented in Sage, so I would not say it is universal.
> It sounds like you are suggesting this: for elements of the Permutation
> class:
> 1. define __mult__ to be L to R mult,
> 1. overload __pow__ to be R to L mult, if both args are perms, and
> to be the usual power if the right arg is an int.
> If that is what you are saying, then I vote +1 for it (provided
> it is clearly documented as usual).

conjugate has already been defined as ~p, so that's covered
p**i is defined for i and integer

I can try making the p**p to be RL multiplication. I had another idea,
however: I could enhance instantiation to accept the Mul syntax and
make that R to L by default so Permutation([(1,2),(2,3)]) gives
Permutation([0, 3, 1, 2]). If I did that, would the overloading of
power be necessary? Instantiation could even take a list of
Permutations and, again, return the R to L-computed permutation, e.g.
Permutation([a,b,c]) would give a(b(c)).

[David Joyner]

On Sun, Aug 26, 2012 at 6:21 AM, Chris Smith <smi...@gmail.com> wrote:

...

> conjugate has already been defined as ~p, so that's covered
> p**i is defined for i and integer
>
> I can try making the p**p to be RL multiplication. I had another idea,
> however: I could enhance instantiation to accept the Mul syntax and
> make that R to L by default so Permutation([(1,2),(2,3)]) gives
> Permutation([0, 3, 1, 2]). If I did that, would the overloading of
> power be necessary? Instantiation could even take a list of
> Permutations and, again, return the R to L-computed permutation, e.g.
> Permutation([a,b,c]) would give a(b(c)).

That sounds okay with me too.
Offhand, I slightly prefer the other suggestion, as I'd expect some sort of
error message returned if the cycles are not disjoint. Say I mistakenly
enter a non-disjoint cycle (making a typo, say). I'd expect to see an error
rather than an unexpected error.
Which ever is easier to implement and others are happy with.

[Chris Smith]

Here's another idea: create a DisjointCycle object for which
multiplication is R to L. In use it would look like this:

>>> C = DisjointCycle
>>> C(1, 2)*C(2, 3)
(1, 3, 2)
>>> Permutation(_).array_form(0)
[0, 3, 1, 2]

/c

[David Joyner]

How would these be used to construct permutation group?
If you used elements of this class then the elements of a
perm group would not be Perms but DisjointCycles?

> /c

[Aleksandar Makelov]

Hi all,

can't we just make one or the other way of multiplication (L to R or R to L) canonical for the combinatorics module, regardless of whether the permutation is an array form or a cyclic form? After all, it's the same mathematical object with a different representation. Moreover, it's legitimate (and I think that this is a nice feature since it adds more flexibility for handling permutations) to do something like this:
>>> Permutation([[0, 1],[2, 3]])*Permutation([0, 2, 1, 3]) (sorry if they commute... imagine they don't :) )
Is it going to multiply from left to right or from right to left?

I guess it'd be better to make g*h mean "first apply g, then h", since that's how other CAS that handle permutations do it. Currently, the * method converts both permutations to array form and interprets g*h as "first apply h, then g". It'll take a lot of switching all around the combinatorics module, but seems doable.

Cheers,

Alex

[Aaron Meurer]

I agree with this. Just pick a convention and stick with it. 

By the way, I seem to remember a PR that implemented ** as conjugation. Was this never merged?

Aaron Meurer

[Chris Smith]

On Sun, Aug 26, 2012 at 7:50 PM, David Joyner <wdjo...@gmail.com> wrote:
> On Sun, Aug 26, 2012 at 9:39 AM, Chris Smith <smi...@gmail.com> wrote:
>> Here's another idea: create a DisjointCycle object for which
>> multiplication is R to L. In use it would look like this:
>>
>>>>> C = DisjointCycle
>>>>> C(1, 2)*C(2, 3)
>> (1, 3, 2)
>>>>> Permutation(_).array_form(0)
>> [0, 3, 1, 2]
>>
>
> How would these be used to construct permutation group?
> If you used elements of this class then the elements of a
> perm group would not be Perms but DisjointCycles?
>

in order to preserve the R to L multiplication, yes, they would have
to stay DC. But to convert to Permutation I would allow Permutation to
accept DC as shown above. DisjointCycle is a defaultdict that gives a
value equal to the key. Multiplication switches around the entries. If
an element hasn't been addressed it returns itself. So in c, the first
element, 3, is at position 1 whereas in

>>> C(0, 1)*C(1,2)
(0, 2, 1)

the first 0 is at position 0 and in

>>> C(3, 4)*C(4, 5)
(3, 5, 4)

the first position is at 3. Conversion to array form will fill in the
missing values as in

>>> [_[i] for i in range(6)]
[0, 1, 2, 3, 5, 4]

/c

[Chris Smith]

On Sun, Aug 26, 2012 at 8:01 PM, Aleksandar Makelov
<amak...@college.harvard.edu> wrote:
> Hi all,
>
> can't we just make one or the other way of multiplication (L to R or R to L)
> canonical for the combinatorics module, regardless of whether the
> permutation is an array form or a cyclic form? After all, it's the same
> mathematical object with a different representation. Moreover, it's
> legitimate (and I think that this is a nice feature since it adds more
> flexibility for handling permutations) to do something like this:
>>>> Permutation([[0, 1],[2, 3]])*Permutation([0, 2, 1, 3]) (sorry if they
>>>> commute... imagine they don't :) )
> Is it going to multiply from left to right or from right to left?
>

This is L to R and if I try change that it lots of things break.
That's my motivation to allow a DisjointCycle object that allows for a
R to L parsing.

And note that there is a difference between entering a permutation in
terms of cycles where no cycles contain common elements [(1, 2),(4,
5)] and one where they do [(1, 2),(2, 3)]. The latter are currently
disallowed by Permutation by could be entered (if I move that
direction) as C(1, 2)*C(2, 3) where C is the DisjointCycle object.

> I guess it'd be better to make g*h mean "first apply g, then h", since
> that's how other CAS that handle permutations do it.

According to David, this is not the case. e.g. in gap (1, 2)*(2, 3)
gives a R to L multiplication of those cycles.

> Currently, the * method
> converts both permutations to array form and interprets g*h as "first apply
> h, then g".

Alas, it doesn't: a*b is computed as

[a[i] for i in b]

which means "use b to select from a" which means that b was applied
first. If it were L to R it would be

[b[i] for i in a]

And if done in that form, lots of things break (as we might expect).

Personally, L to R makes a lot of sense. When I worked out the
polyhedron transformations I used a 2-permutation basis to work out
the different permutations corresponding, for example, to rotation
through a vertex. Say my basis was p0 and p1. I imagined that to get
to the same place as a vertex rotation I would have to do p0 and p1 3
times so I wrote the permutation as p0*p1**3. This is interpreted in
the normal L to R reading: do p0 once and p1 three times.

/c

[Chris Smith]

OK, it can be almost as nice as gap, but I don't think I can change
the fact that for python ()*() isn't defined. But if I start the
multiplication with a DisjointCycle instance then

>>> C = DisjointCycle()
>>> C*(1,2)*(2,3)
[(1, 2, 3)]
>>> C*(1,2)*(2,3)*(4,5)
[(1, 2, 3), (4, 5)]

/c

[David Joyner]

On Sun, Aug 26, 2012 at 9:27 PM, Chris Smith <smi...@gmail.com> wrote:
> On Sun, Aug 26, 2012 at 8:01 PM, Aleksandar Makelov
> <amak...@college.harvard.edu> wrote:

...

>
>> I guess it'd be better to make g*h mean "first apply g, then h", since
>> that's how other CAS that handle permutations do it.
>
> According to David, this is not the case. e.g. in gap (1, 2)*(2, 3)
> gives a R to L multiplication of those cycles.
>

I would call gap's method L or R: first see what happens to 1 as you
scan left to right:
1 goes to 2 which goes to 3, so 1 goes to 3, etc, This gives (1,3,2).

[Chris Smith]

>>> I guess it'd be better to make g*h mean "first apply g, then h", since
>>> that's how other CAS that handle permutations do it.
>>
>> According to David, this is not the case. e.g. in gap (1, 2)*(2, 3)
>> gives a R to L multiplication of those cycles.
>>
>
> I would call gap's method L or R: first see what happens to 1 as you
> scan left to right:
> 1 goes to 2 which goes to 3, so 1 goes to 3, etc, This gives (1,3,2).

Very interesting way to look at it. Since I am looking at these as
shorthand for permutations, and you get the correct answer by applying
the rightmost permutations first. But if you think of trying to find
the correct cycle notation, you do so by reading left to right. So
perhaps the docstring should say that products of disjoint cycles
computes the product of the corresponding permutations from right to
left.

Note that at least one author (
http://www.usna.edu/Users/math/wdj/tonybook/gpthry/node13.html ) gets
this wrong, reconstructing the *cycle* by reading right to left. To
get the right permutation, apply permutations from right to left for a
given cycle notation; to get the cycle notation correct, read from
left to right. The example is

(1,2)*(2,4,5)*(1,3)*(1,2,5)

Here are the permutations (in left to right order) starting after the
identity with the result of applying that to the previous result:

[0, 1, 2, 3, 4, 5]
[0, 2, 1, 3, 4, 5] -> [0, 2, 1, 3, 4, 5]
[0, 1, 4, 3, 5, 2] -> [0, 2, 4, 3, 5, 1]
[0, 3, 2, 1, 4, 5] -> [0, 3, 4, 2, 5, 1]
[0, 2, 5, 3, 4, 1] -> [0, 4, 1, 2, 5, 3]

That answer, in cyclic form is, [[1, 4, 5, 3, 2]]. This is the result
you get when you process permutations from left to right or read cycle
notation from right to left.

If you do the reverse (apply permutations from right to left) or
cycles from left to right you get [[1, 4], [2, 3]] .

I'll add a note to the documentation.

[Tom Bachmann]

I'm not sure if I'm helping, but I'm also not sure if I understand what
you are saying.

Let us fix a set X we are considering the permutation group of, below I
will take X = {1, 2, 3, 4, 5}. A permutation of X is by definition a
bijective function f:X->X. It is specified uniquely by providing the
image of every element. We can write this in the short form
[f(1), f(2), f(3), f(4), f(5)]. In this way, every permutation is
represented by an array of constant size.

Now let's talk about cycles. By definition, a cycle is an ordered subset
of X. In general, the cycle (a_1 ... a_n) represents the unique
permutation f with f(a_1) = a_2, ..., f(a_n) = a_1, and f(x) = x for all
x not in {a_1, .., a_n}. For example, the cycle (1 2 3) denotes the
permutation [2, 3, 1, 4, 5].
We can identify the set of cycles with a subset of the set of permutations.

Now let's consider composition. There are two schools of thought. Let me
write * for "ordinary" (where I come from) composition, and . for
"weird" composition. By definition, if f, g are permutations, then the
permutation f*g is the unique mapping such that (f*g)(x) = f(g(x))
["apply right to left"], whereas (f.g)(x) = g(f(x)) ["apply left to
right"]. [*]

Observe now that any permutation can be written uniquely (up to
ordering) as a product of disjoint cycles. That is, if f is any
permutation, then there exists distinct and disjoint cycles c_1, ..,
c_n, such that c_1*...*c_n = f = c_1.c_2 ... .c_n [i.e. the two modes of
composition agree for disjoint cycles]. Moreover the order of
composition is irrelevant, and if d_1, .., d_m are another set of
disjoint cycles usch that f = d_1, .., d_m then {c_1, .., c_n} = {d_1,
.., d_m} [in particular n = m].

Finally, composition of cycles. Since we have already defined
composition of permutations (in fact in two ways), and since finding the
disjoint cycle composition of a permutation is easy, there is actually
not much to say here. Let's just consider an example:

(1 2 3)*(3 4 5) = (1 2 3 4 5) = [2, 3, 4, 5, 1]
(1 2 3).(3 4 5) = (1 2 4 5 3) = [2, 4, 1, 5, 3]

I can see the cycles easily as follows: in either case, I first write
down the 1. Then I figure out where 1 is mapped. In the first case, (3 4
5) is applied first, which fixes 1, and then (1 2 3) is applied, which
maps 1 to 2, so 1 is mapped to 2. In the second case 1 is first mapped
to 2 and then 2 is fixed, so same effect. Now to continue the cycle, I
figure out where 2 is mapped. In the first case, (3 4 5) fixes 2, and
then (1 2 3) maps it to 3, so 2 is mapped to 3. In the second case, (1 2
3) maps 2 to 3, and then (3 4 5) maps 3 to 4. Hence 2 is mapped to 4.
In the first case I continue by figuring out where 3 is mapped, in the
second by figuring out where 4 is mapped.

I'm writing this chiefly because it shows that, in "ordinary" (right to
left) composition, the cycle notation is obtained by reading right to
left! Similarly in left to right composition you read cycles left to right.

Probably all this is obvious to you, and I'm just misreading your statement.

[*] Note that this can be made to look more sensible (for some
definitions of sensible), by writing *arguments* on the left: applying f
to x can be written as (x)f, and then (x)(f.g) = ((x)f)g ...

[David Joyner]

On Mon, Aug 27, 2012 at 12:05 PM, Chris Smith <smi...@gmail.com> wrote:

...

>
> Note that at least one author (
> http://www.usna.edu/Users/math/wdj/tonybook/gpthry/node13.html ) gets
> this wrong, reconstructing the *cycle* by reading right to left. To
> get the right permutation, apply permutations from right to left for a
> given cycle notation; to get the cycle notation correct, read from
> left to right. The example is
>
> (1,2)*(2,4,5)*(1,3)*(1,2,5)
>

Agreed, Tony gets it wrong. Here is the correct answer, according to Gap,
which is also exactly what you say it should be:

gap> (1,2)*(2,4,5)*(1,3)*(1,2,5);
(1,4)(2,3)

I'll tell him - thanks.

[David Joyner]

On Mon, Aug 27, 2012 at 2:26 PM, Tom Bachmann <e_m...@web.de> wrote:
> I'm not sure if I'm helping, but I'm also not sure if I understand what you
> are saying.
>
> Let us fix a set X we are considering the permutation group of, below I will
> take X = {1, 2, 3, 4, 5}. A permutation of X is by definition a bijective
> function f:X->X. It is specified uniquely by providing the image of every
> element. We can write this in the short form
> [f(1), f(2), f(3), f(4), f(5)]. In this way, every permutation is
> represented by an array of constant size.
>
> Now let's talk about cycles. By definition, a cycle is an ordered subset of
> X. In general, the cycle (a_1 ... a_n) represents the unique permutation f
> with f(a_1) = a_2, ..., f(a_n) = a_1, and f(x) = x for all x not in {a_1,
> .., a_n}. For example, the cycle (1 2 3) denotes the permutation [2, 3, 1,
> 4, 5].
> We can identify the set of cycles with a subset of the set of permutations.
>
> Now let's consider composition. There are two schools of thought. Let me
> write * for "ordinary" (where I come from) composition, and . for "weird"
> composition. By definition, if f, g are permutations, then the permutation
> f*g is the unique mapping such that (f*g)(x) = f(g(x)) ["apply right to
> left"], whereas (f.g)(x) = g(f(x)) ["apply left to right"]. [*]
>

This is correct *as functions*.
If you do this *as permutations* (which *act* on a set and are not
just functions),
then you want the permutations to form an "action" on the set.
The way you want to do it, they aren't an action:

if g1 = (1,2) and g2 = (2,4,5) then (g1*g2)(2) \not= g1(g2(2)):

sage: G = SymmetricGroup(5)
sage: g1 = G([(1,2)])
sage: g2 = G([(2,4,5)])
sage: g2(2)
4
sage: g3 = g1*g2
sage: a = g2(2); a
4
sage: b = g1(a); b
4
sage: g3(2)
1

It is very important for many people that the group
of permutations yields a group action on the set.

> Observe now that any permutation can be written uniquely (up to ordering) as

...

[Chris Smith]

> Agreed, Tony gets it wrong. Here is the correct answer, according to Gap,
> which is also exactly what you say it should be:
>
> gap> (1,2)*(2,4,5)*(1,3)*(1,2,5);
> (1,4)(2,3)
>
> I'll tell him - thanks.

Thanks -- it was late and I didn't look for a feedback link. But in
looking today, I see you are a good person to let know about this (and
thanks for getting this feedback to him). I appreciate the detail with
which his work was presented.

[Tom Bachmann]

I'm not sure I get this. Since you are much more knowledgable than me
maybe I should just shut up, but as far as I know, a (left) action of a
group G on a set S is a map phi: GxS -> S, where I shall write g(s) for
phi(g, s) if g in G and s in S. Then the axioms are:

- e(s) = s for all s
- g(h(s)) = (gh)(s) for all s in S, g, h in G


If we let Sym(S) denote the symmetric group on S, by which I mean the
set of all bijections S->S with the "ordinary" (left, or *) composition,
then I believe it is easy to check that an action is the same as a
homomorphism from G to Sym(S). Anyway, we *obviously* want (g1*g2)(2) =
g1(g2(2)).

Wikipedia agrees with this definition of (left) action, btw.

We can similarly define a right action. For example, if Sym'(S) denotes
Sym(S) with the other composition law, then a right action is a
homomorphism G->Sym'(S). More explicitly, it is a map phi:SxG -> S, such
that

- (s)e = s for all s in S
- ((s)g)h = (s)(gh) for all s, g, h.

Where am I wrong?


I think this all just boils down to the fact that for actual
computations with permutations, it is more convenient to work with the
"." operation (i.e. composition on the left) than with the "*"
operation, essentially because we read from left to right. Much of the
confusion probably stems from the fact that these conventions are
completely equivalent (Taking opposite groups interchanges left and
right actions, and the opposite group is naturally isomorphis to the
group we started with).

Thanks,
Tom

[David Joyner]

On Tue, Aug 28, 2012 at 12:33 PM, Tom Bachmann <e_m...@web.de> wrote:
> On 27.08.2012 22:52, David Joyner wrote:
>>

...

>> The way you want to do it, they aren't an action:
>>
>> if g1 = (1,2) and g2 = (2,4,5) then (g1*g2)(2) \not= g1(g2(2)):
>>
>
> I'm not sure I get this. Since you are much more knowledgable than me maybe
> I should just shut up, but as far as I know, a (left) action of a group G on
> a set S is a map phi: GxS -> S, where I shall write g(s) for phi(g, s) if g
> in G and s in S. Then the axioms are:
>
> - e(s) = s for all s
> - g(h(s)) = (gh)(s) for all s in S, g, h in G
>
>
> If we let Sym(S) denote the symmetric group on S, by which I mean the set of
> all bijections S->S with the "ordinary" (left, or *) composition, then I
> believe it is easy to check that an action is the same as a homomorphism
> from G to Sym(S). Anyway, we *obviously* want (g1*g2)(2) = g1(g2(2)).
>
> Wikipedia agrees with this definition of (left) action, btw.
>
> We can similarly define a right action. For example, if Sym'(S) denotes
> Sym(S) with the other composition law, then a right action is a homomorphism
> G->Sym'(S). More explicitly, it is a map phi:SxG -> S, such that
>
> - (s)e = s for all s in S
> - ((s)g)h = (s)(gh) for all s, g, h.
>
> Where am I wrong?

I think you are saying if you use one definition of the product,
it is a left action and the other definition of product is a right action.
Good point. You are correct. So my argument that the R-L product
is not an action is wrong. Thanks for pointing that out.

I still take the position that the L-R product is the usual way it is
done in computer algebra systems.

[Chris Smith]

Permutations now work from R to L in Permutation and Cycle form. lmul is
the public classmethod to do otherwise: Permutation.lmul(a, b) = b*a

What does anyone think about always storing a permutation in array
form? It can be viewed in cyclic_form with the cyclic_form method (or
converted to a Cycle with Cycle). This would clean up the
instantiation problem now that arises because if the whole cycle is
not stored then you need two args (cycles and size) to reconstruct as
Permutation(*p.args) and right now, size is not being stored as an
arg.

/c

[Chris Smith]

> I still take the position that the L-R product is the usual way it is
> done in computer algebra systems.

Do you mean R to L?

[Chris Smith]

>>> from sympy.combinatorics import *
>>> Cycle()*(1,2)*(2,3)
[(1, 3, 2)]
>>> _.as_list()
[0, 3, 1, 2]
>>> Permutation([[2,3]],size=4).array_form
[0, 1, 3, 2]
>>> Permutation([[1,2]],size=4).array_form
[0, 2, 1, 3]

So using the (1,2) permutation to select from the (2,3) one gives the
final answer of [0, 3, 1, 2] (applied the (1,2) last, hence R to L)

[David Joyner]

On Tue, Aug 28, 2012 at 5:54 PM, Chris Smith <smi...@gmail.com> wrote:
>>>> from sympy.combinatorics import *
>>>> Cycle()*(1,2)*(2,3)
> [(1, 3, 2)]

I call this L-R multiplication, because you "plug" 1 in from the left and
see what cycle it belongs to by scanning L to R, then plug in the next
smallest integer outside that cycle and see what cycle it belongs to, etc
This agrees with Sage and Gap:

sage: G = SymmetricGroup(5)
sage: g1 = G([(1,2)])

sage: g2 = G([(2,3)])
sage: g1*g2
(1,3,2)

>>>> _.as_list()
> [0, 3, 1, 2]
>>>> Permutation([[2,3]],size=4).array_form
> [0, 1, 3, 2]
>>>> Permutation([[1,2]],size=4).array_form
> [0, 2, 1, 3]

>>> Permutation([[1,2]],size=4)*Permutation([[2,3]],size=4)
> Permutation([0, 2, 3, 1])

Which is (2,1,3).

>
> So using the (1,2) permutation to select from the (2,3) one gives the
> final answer of [0, 3, 1, 2] (applied the (1,2) last, hence R to L)
>

[Chris Smith]

On Wed, Aug 29, 2012 at 3:58 AM, David Joyner <wdjo...@gmail.com> wrote:
> On Tue, Aug 28, 2012 at 5:54 PM, Chris Smith <smi...@gmail.com> wrote:
>>>>> from sympy.combinatorics import *
>>>>> Cycle()*(1,2)*(2,3)
>> [(1, 3, 2)]
>
> I call this L-R multiplication, because you "plug" 1 in from the left and
> see what cycle it belongs to by scanning L to R, then plug in the next
> smallest integer outside that cycle and see what cycle it belongs to, etc
> This agrees with Sage and Gap:

OK, then whatever we call it hopefully the doc strings are clear that
I've written?

>
> sage: G = SymmetricGroup(5)
> sage: g1 = G([(1,2)])
> sage: g2 = G([(2,3)])
> sage: g1*g2
> (1,3,2)
>

...

>> Permutation([0, 2, 3, 1])
>
> Which is (2,1,3).

So we agree on the result.

I'm very interested to see how using Permutaiton and Cycle feels to
you in the current branch. Any comment welcome. I think it's in good
shape now.

[David Joyner]

I did

she:sympy davidjoyner$ git checkout smichr/combinatorics
HEAD is now at b4bb058... permutation: add 0 to non-0-based perm

but don't seem to have Cycle defined:

>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>> from sympy.combinatorics import *
>>> a = Cycle()*(1,2)
Traceback (most recent call last):
File "<console>", line 1, in <module>
NameError: name 'Cycle' is not defined

[Chris Smith]

>
> I did
>
> she:sympy davidjoyner$ git checkout smichr/combinatorics
> HEAD is now at b4bb058... permutation: add 0 to non-0-based perm
>
> but don't seem to have Cycle defined:
>
>>>> from sympy.combinatorics.perm_groups import PermutationGroup
>>>> from sympy.combinatorics import *
>>>> a = Cycle()*(1,2)
> Traceback (most recent call last):
> File "<console>", line 1, in <module>
> NameError: name 'Cycle' is not defined
>

Sorry -- caught up with that 20 minutes later. Could you please try again?

[David Joyner]

Nope. In fact, I deleted sympy entirely and started form a new version using

git clone git://github.com/sympy/sympy.git
cd sympy
git remote add smichr https://github.com/smichr/sympy
git fetch smichr
git checkout smichr/combinatorics

and then got this:

>>> from sympy.combinatorics import *
>>> from sympy.combinatorics.perm_groups import *
>>> C = DisjointCycle()

Traceback (most recent call last):
File "<console>", line 1, in <module>

NameError: name 'DisjointCycle' is not defined

[Chris Smith]

It's just called Cycle now (see docstring).

/c

[David Joyner]

On Wed, Aug 29, 2012 at 7:25 AM, Chris Smith <smi...@gmail.com> wrote:

...

>> Traceback (most recent call last):
>> File "<console>", line 1, in <module>
>> NameError: name 'DisjointCycle' is not defined
>>
>
> It's just called Cycle now (see docstring).
>

Is this supposed to happen?

>>> C = Cycle()
>>> a = Cycle()*(1,2)
>>> b = Cycle()*(2,3)
>>> G = PermutationGroup([a, b])

Traceback (most recent call last):
File "<console>", line 1, in <module>

File "/Users/davidjoyner/pythonfiles/sympy/sympy/combinatorics/perm_groups.py",
line 381, in __new__
obj._degree = obj._generators[0].size
AttributeError: 'Cycle' object has no attribute 'size'


> /c

[Chris Smith]

>>>> C = Cycle()
>>>> a = Cycle()*(1,2)
>>>> b = Cycle()*(2,3)
>>>> G = PermutationGroup([a, b])
> Traceback (most recent call last):
> File "<console>", line 1, in <module>
> File "/Users/davidjoyner/pythonfiles/sympy/sympy/combinatorics/perm_groups.py",
> line 381, in __new__
> obj._degree = obj._generators[0].size
> AttributeError: 'Cycle' object has no attribute 'size'

Yes. Cycles are a really limited representation of a Permutation that
are nice for working with when multiplying them. The problem is that
each of them has whatever elements have been included thus far (so `a`
has 1 and 2 while b has 2 and s). Anything that works with
permutations wants them to be of equal length and that's where you
have to convert from Cycle to Permutation using size:

PermutationGroup([Permutation(w, size=4) for w in (a,b)]) should work:

```

>>> from sympy.combinatorics.perm_groups import *
>>> from sympy.combinatorics import *
>>> a,b=Cycle(1,2),Cycle(2,3)
>>> PermutationGroup([Permutation(w, size=4) for w in (a,b)])
PermutationGroup([Permutation([0, 2, 1, 3]), Permutation([0, 1, 3, 2])])
>>>

```

[David Joyner]

I guess the bottom line is I'm wondering how to enter the generators
of the Rubik's cube group, eg at

http://www.gap-system.org/Doc/Examples/rubik.html
or
http://www.permutationpuzzles.org/rubik/webnotes/sm485_3b.txt

Is there an easy way to do that?

[Chris Smith]

On Thu, Aug 30, 2012 at 5:19 PM, David Joyner <wdjo...@gmail.com> wrote:
> I guess the bottom line is I'm wondering how to enter the generators
> of the Rubik's cube group, eg at

>>> from sympy.combinatorics.generators import rubik_cube_generators
>>> gens = rubik_cube_generators()

A single one might be entered in cycle notation as:

Permutation([(0, 2, 7, 5), (1, 4, 6, 3), (8, 32, 24, 16), (9, 33, 25,
17), (10, 34, 26, 18)])

[David Joyner]

When I enter that I get an error:

>>> Permutation([(0, 2, 7, 5), (1, 4, 6, 3), (8, 32, 24, 16), (9, 33, 25,17), (10, 34, 26, 18)])

Traceback (most recent call last):
File "<console>", line 1, in <module>

File "/Users/davidjoyner/pythonfiles/sympy/sympy/combinatorics/permutations.py",
line 455, in __new__
(len(temp) - 1))
ValueError: Integers 0 through 19 must be present or (for cyclic
notation) size must be given.

[Chris Smith]

>
> Permutation([(0, 2, 7, 5), (1, 4, 6, 3), (8, 32, 24, 16), (9, 33, 25,17), (10, 34, 26, 18)])

Sorry, enter that as

Permutation([(0, 2, 7, 5), (1, 4, 6, 3), (8, 32, 24, 16), (9, 33,

25,17), (10, 34, 26, 18)] , size=48)

[David Joyner]

Thanks. Here we are:-)


>>> F = Permutation([(17,19,24,22),(18,21,23,20),( 6,25,43,16),( 7,28,42,13),( 8,30,41,11)], size=49)
>>> B = Permutation([(33,35,40,38),(34,37,39,36),( 3, 9,46,32),( 2,12,47,29),( 1,14,48,27)], size=49)
>>> L = Permutation([( 9,11,16,14),(10,13,15,12),( 1,17,41,40),( 4,20,44,37),( 6,22,46,35)], size=49)
>>> R = Permutation([ (25,27,32,30),(26,29,31,28),( 3,38,43,19),( 5,36,45,21),( 8,33,48,24)], size=49)
>>> U = Permutation([ ( 1, 3, 8, 6),( 2, 5, 7, 4),( 9,33,25,17),(10,34,26,18),(11,35,27,19)], size=49)
>>> D = Permutation([ (41,43,48,46),(42,45,47,44),(14,22,30,38),(15,23,31,39),(16,24,32,40)], size=49)
>>> G = PermutationGroup([F,B,L,R,U,D])
>>> G.order()
43252003274489856000
>>> Z = G.center()
>>> Z.order()
2

[Chris Smith]

On Thu, Aug 30, 2012 at 8:22 PM, David Joyner <wdjo...@gmail.com> wrote:
> On Thu, Aug 30, 2012 at 10:20 AM, Chris Smith <smi...@gmail.com> wrote:
>>>
>>> Permutation([(0, 2, 7, 5), (1, 4, 6, 3), (8, 32, 24, 16), (9, 33, 25,17), (10, 34, 26, 18)])
>>
>> Sorry, enter that as
>>
>> Permutation([(0, 2, 7, 5), (1, 4, 6, 3), (8, 32, 24, 16), (9, 33,
>> 25,17), (10, 34, 26, 18)] , size=48)
>
> Thanks. Here we are:-)
>
>
>>>> F = Permutation([(17,19,24,22),(18,21,23,20),( 6,25,43,16),( 7,28,42,13),( 8,30,41,11)], size=49)
>>>> B = Permutation([(33,35,40,38),(34,37,39,36),( 3, 9,46,32),( 2,12,47,29),( 1,14,48,27)], size=49)
>>>> L = Permutation([( 9,11,16,14),(10,13,15,12),( 1,17,41,40),( 4,20,44,37),( 6,22,46,35)], size=49)
>>>> R = Permutation([ (25,27,32,30),(26,29,31,28),( 3,38,43,19),( 5,36,45,21),( 8,33,48,24)], size=49)
>>>> U = Permutation([ ( 1, 3, 8, 6),( 2, 5, 7, 4),( 9,33,25,17),(10,34,26,18),(11,35,27,19)], size=49)
>>>> D = Permutation([ (41,43,48,46),(42,45,47,44),(14,22,30,38),(15,23,31,39),(16,24,32,40)], size=49)
>>>> G = PermutationGroup([F,B,L,R,U,D])
>>>> G.order()
> 43252003274489856000
>>>> Z = G.center()
>>>> Z.order()
> 2

I wish I had the warm fuzzyz that come from seeing with the
heart...but I don't understand this topic well (though I am learning).
What is nice to see is that this agrees with this:


>>> from sympy.combinatorics.generators import *
>>> [w for w in dir() if 'ub' in w]
['Subs', 'rubik_cube_generators', 'subresultants', 'subsets']
>>> from sympy.combinatorics.perm_groups import *
>>> G=PermutationGroup(rubik_cube_generators())
>>> G.order()
43252003274489856000L
>>> Z=G.center()
>>> Z.order()
2

One thing that interests me is whether there is a decomposition method
for finding how a given set of permutations might produce a a given
permutation, like `FooPerm.factor([P1, P2]) -> (0, 3) if FooPerm is
just P2**3 or (1, 2) if P1*P2**2.`

[Chris Smith]

>
>>>> F = Permutation([(17,19,24,22),(18,21,23,20),( 6,25,43,16),( 7,28,42,13),( 8,30,41,11)], size=49)
>>>> B = Permutation([(33,35,40,38),(34,37,39,36),( 3, 9,46,32),( 2,12,47,29),( 1,14,48,27)], size=49)
>>>> L = Permutation([( 9,11,16,14),(10,13,15,12),( 1,17,41,40),( 4,20,44,37),( 6,22,46,35)], size=49)
>>>> R = Permutation([ (25,27,32,30),(26,29,31,28),( 3,38,43,19),( 5,36,45,21),( 8,33,48,24)], size=49)
>>>> U = Permutation([ ( 1, 3, 8, 6),( 2, 5, 7, 4),( 9,33,25,17),(10,34,26,18),(11,35,27,19)], size=49)
>>>> D = Permutation([ (41,43,48,46),(42,45,47,44),(14,22,30,38),(15,23,31,39),(16,24,32,40)], size=49)
>>>> G = PermutationGroup([F,B,L,R,U,D])
>>>> G.order()
> 43252003274489856000
>>>> Z = G.center()
>>>> Z.order()
> 2

I see you used the "extra 0" form -- at least I assume that's why you
used 49 instead of 48. When I did this, the only test that failed as
G.orbits(rep=True) which came back as [0, 1, 2] instead of [0,
1]...I'm not sure what that means except that [1, 2] is the same as
[0, 1] but shifted up 1 because of the extra 0?

[David Joyner]

Yes, I was just to lazy to do the shift myself. Really, it is better to have the
shift, as you did in an earlier email. BTW, thanks for showing me the
rubik_cube_generators() function. I didn't know about that!

[Chris Smith]

David, could you entertain a question here:

I wrote a routine to generate permutations of an nxn Rubik's cube. I
enter into a PermutationGroup the permutation of the faces after these
standard rotations:

1) cw rotation of cube from front
2) cw rotation of cube from top
3) n//2 + n%2 cw slice rotations from the front (e.g. just the front
1/nth of the cube, then the 2/nth slice of the cube, ..., until the
middle or the one before the middle).

I checked with an appropriately numbered tissue box that the right
permutations are being returned. And these seem like they should be a
sufficient basis for obtaining any orientation of the cube. But when I
check the order I find:

>>> from sympy.combinatorics import *
>>> for i in range(1, 4):
... print i, RubikGroup(i).order()
...
1 24
2 88179840
3 1038048078587756544000
>>> RubikGroup(4).order()
43252003274489856000
(and if I use the generators my routine generates, recursion error
prevents the order from being computed)

Is there any easy way that you can explain to me why the 3x3's order
is larger than the 4's when giving those particular permutations?

Is this just a suboptimal group? What permutations make the optimal
group? With the code I have I can construct the permutation for any
sequence of turns that should be in the optimal group.

[Chris Smith]

oops -- I see that the 43252003274489856000 is for a 3x3 cube. I'll
correct the code and recommit.

[David Joyner]

On Fri, Aug 31, 2012 at 9:03 AM, Chris Smith <smi...@gmail.com> wrote:
> David, could you entertain a question here:
>
> I wrote a routine to generate permutations of an nxn Rubik's cube. I
> enter into a PermutationGroup the permutation of the faces after these
> standard rotations:
>
> 1) cw rotation of cube from front
> 2) cw rotation of cube from top
> 3) n//2 + n%2 cw slice rotations from the front (e.g. just the front
> 1/nth of the cube, then the 2/nth slice of the cube, ..., until the
> middle or the one before the middle).

In the "odd" cases, the center cubie of each face should be fixed.
This fixes an orientation of the cube in space. In the "even" cases, I'm
not sure how to fix an orientation.

>
> I checked with an appropriately numbered tissue box that the right
> permutations are being returned. And these seem like they should be a
> sufficient basis for obtaining any orientation of the cube. But when I
> check the order I find:
>
>>>> from sympy.combinatorics import *
>>>> for i in range(1, 4):
> ... print i, RubikGroup(i).order()
> ...
> 1 24
> 2 88179840
> 3 1038048078587756544000

When you fix an orientation, this should be 4.3x10^19, roughly.

>>>> RubikGroup(4).order()
> 43252003274489856000

This is 4.3x10^19, roughly. Did you define RubikGroup(4) to be the 3x3
Rubik's cube group?

> (and if I use the generators my routine generates, recursion error
> prevents the order from being computed)
>
> Is there any easy way that you can explain to me why the 3x3's order
> is larger than the 4's when giving those particular permutations?
>
> Is this just a suboptimal group? What permutations make the optimal
> group? With the code I have I can construct the permutation for any
> sequence of turns that should be in the optimal group.
>

[Chris Smith]

> In the "odd" cases, the center cubie of each face should be fixed.
> This fixes an orientation of the cube in space. In the "even" cases, I'm
> not sure how to fix an orientation.

I see. The numbers work now:

>>> for i in range(1, 4):

... print i, PermutationGroup(rubik_cube(i)).order()

...
1 24
2 88179840

3 43252003274489856000

for the 2x2 when you divide by 24 you get the correct value

>>> PermutationGroup(rubik_cube(2)).order()/24
3674160

And case 4 cannot be handled recursively to calculate the order, but
it can still be manipulated (e.g. rotated)

>>> R4=PermutationGroup(rubik_cube(4))
>>> R4.make_perm([0])
Permutation([76, 72, 68, 64, 77, 73, 69, 65, 78, 74, 70, 66, 79, 75,
71, 67, 28, 24, 20, 16, 29, 25, 21, 17, 30, 26, 22, 18, 31, 27, 23,
19, 12, 8, 4, 0, 13, 9, 5, 1, 14, 10, 6, 2, 15, 11, 7, 3, 51, 55, 59,
63, 50, 54, 58, 62, 49, 53, 57, 61, 48, 52, 56, 60, 92, 88, 84, 80,
93, 89, 85, 81, 94, 90, 86, 82, 95, 91, 87, 83, 44, 40, 36, 32, 45,
41, 37, 33, 46, 42, 38, 34, 47, 43, 39, 35])

/c

[Aaron Meurer]

So what's the status of all this? Are we going to make any API
changes? If so, we need to get them into the release branch. This is
currently the only thing that's keeping me from making the release
candidate.

Aaron Meurer

[Chris Smith]

On Sat, Sep 1, 2012 at 10:39 PM, Aaron Meurer <asme...@gmail.com> wrote:
> So what's the status of all this? Are we going to make any API
> changes? If so, we need to get them into the release branch. This is
> currently the only thing that's keeping me from making the release
> candidate.

Let me squash everything together so I can see what has changed.

[Chris Smith]

The big changes that breaks compatibility in a subtle way is that
Permutation now multiplies from R to L. There were lots of other
changes:

Some private functions underwent name changes.

Some public methods were changed (name changes), moved or deleted.

Permutation accepts args not *args and recognizes a size keyword.

cyclic_form returns the abbreviated form (without singletons) and
`reduced_cyclic_form` was changed to `full_cyclic_form`.

I've boosted coverage to 100% on a few of the files and added tests to
boost the others. I'm feeling good about the changes but someone else
needs to give it the final ok.

[David Joyner]

On Sat, Sep 1, 2012 at 1:39 PM, Chris Smith <smi...@gmail.com> wrote:
> The big changes that breaks compatibility in a subtle way is that

What does this mean?

> Permutation now multiplies from R to L. There were lots of other
> changes:
>
> Some private functions underwent name changes.
>
> Some public methods were changed (name changes), moved or deleted.
>
> Permutation accepts args not *args and recognizes a size keyword.
>
> cyclic_form returns the abbreviated form (without singletons) and
> `reduced_cyclic_form` was changed to `full_cyclic_form`.
>
> I've boosted coverage to 100% on a few of the files and added tests to
> boost the others. I'm feeling good about the changes but someone else
> needs to give it the final ok.
>

[Chris Smith]

On Sat, Sep 1, 2012 at 11:26 PM, David Joyner <wdjo...@gmail.com> wrote:
> On Sat, Sep 1, 2012 at 1:39 PM, Chris Smith <smi...@gmail.com> wrote:
>> The big changes that breaks compatibility in a subtle way is that
>
> What does this mean?

in master:

>>> Permutation([1, 0, 2])*Permutation([0,2,1])
Permutation([1, 2, 0])

in this PR:

>>> Permutation([1, 0, 2])*Permutation([0,2,1])
Permutation([2, 0, 1])

[David Joyner]

Okay. But does it break lots of code in other modules?

[Chris Smith]

btw, I figured out what the problem with my general rubik generators
was, David:

1) to maintain the orientation of the cube one need only supply as
permutations the permutations corresponding to the motion of the
different rings from 3 sides up to but not including the ring
containing the top left cube.

2) when computing a permutation I moved the cube, made the change, but
didn't put the cube back in its fixed orientation. e.g. to compute the
permutation corresponding to rotating the R face I turned the cube,
rotated the face and recorded the permutation -- I should have (and
now do) re-rotated the cube so the turned face was back on the right.
When I did this correctly, the order is computed correctly. Note: my
generators have a different (and I suppose expectedly so) result for
computations like orbit so I left the old generator there
(rubik_cube_generators) but have the new one for the nxn rubik, too
(rubik) which is called by the new RubikGroup function.

[Chris Smith]

On Sat, Sep 1, 2012 at 11:50 PM, David Joyner <wdjo...@gmail.com> wrote:
> On Sat, Sep 1, 2012 at 1:47 PM, Chris Smith <smi...@gmail.com> wrote:
>> On Sat, Sep 1, 2012 at 11:26 PM, David Joyner <wdjo...@gmail.com> wrote:
>>> On Sat, Sep 1, 2012 at 1:39 PM, Chris Smith <smi...@gmail.com> wrote:
>>>> The big changes that breaks compatibility in a subtle way is that
>>>
>>> What does this mean?
>>
>> in master:
>>
>>>>> Permutation([1, 0, 2])*Permutation([0,2,1])
>> Permutation([1, 2, 0])
>>
>> in this PR:
>>
>>>>> Permutation([1, 0, 2])*Permutation([0,2,1])
>> Permutation([2, 0, 1])
>>
>
>
> Okay. But does it break lots of code in other modules?

Only in combinatorics, but I went through and changed all occurences
to explicit lmul() calls. I know I have all instances covered because
I put an assertion in `__mul__` (assert None) that caused an error to
be raised so I could change foo*bar to lmul(foo, bar). (I think I
looked at coverage to make sure that there were no muls in uncovered
lines, too, but I should double check that.)

[David Joyner]

On Sat, Sep 1, 2012 at 2:08 PM, Chris Smith <smi...@gmail.com> wrote:
> btw, I figured out what the problem with my general rubik generators
> was, David:

Cool!

>
> 1) to maintain the orientation of the cube one need only supply as

...

> (rubik) which is called by the new RubikGroup function.
>

[David Joyner]

Really Aleksander M is the best person to give the okay but it sounds like
he is busy with the first weeks of classes. Since Aaron says this
should be looked
at soon, perhaps I should look at it? If so, is there a ticket
number/link I should
post a review at?

[Chris Smith]

> at soon, perhaps I should look at it? If so, is there a ticket
> number/link I should
> post a review at?

https://github.com/sympy/sympy/pull/1498

[David Joyner]

Thanks. I added some comments there.

[David Joyner]

From there, you posted this question, which might be of more general interest:

"I'm also wondering what SymPy has to offer over sage after seeing how much
work has already gone into sage...can you give any pros to the work that is
being duplicated here?"

I think the main thing to this latest work on group theory in sympy is that
it is a pure python implementation of some very complicated algorithms
in computational group theory. They are, I'm sure, in Gap and I think the
authors of those programs are probably all Gap developers. (Gap is an
interpreted Pascal-like language which is about as fast as Python.)

One pro is that once this filters up to PyMath (a cell-phone app),
one can use sympy's group theory as a stand-alone app on a
cell-phone or tablet. There is a Sage app but it requires an internet
connection.

Gap is included in Sage, but only a small part of Gap has been re-written
in Python (or actually Cython, for greater speed). Mostly, the group theory
computations rely on parsing the commands, passing them to Gap, and
returning them
to Sage. This communication pipeline can be quite complicated to set
up, especially if the output is very large. Of course, Gap has a lot of
group-theory structure which isn't even in Sage as a Python class.
In that case, you basically have to use Gap directly (you can start a
Gap command-line session using the Sage command gap_console()).

Hope these comments help.

[Aaron Meurer]

I also wanted to comment on this, and I'm glad you brought it to the
list. There are several advantages to having things in SymPy even if
they already exist in Sage, not just group theory but all aspects of a
computer algebra system.

First, as David noted, it will be implemented in pure Python. This
has several advantages. One, as David also noted, is that it makes it
much easier to use in environments where installing or compiling a
large binary would be otherwise impossible. This is coupled with the
fact that SymPy has no further dependencies. Mobile phones are one
example of this. Environments where you have no administrational
control over the machine might be another.

Another reason this helps is that, as we all know, Python is a very
nice language to read. So if someone is interested in the
implementation of something, they will probably get much more out of
the implementation in SymPy than the one in, say, Maxima, which is
written in Lisp.

Second is the fact that SymPy can be used as a library. Last time I
checked, this is not doable with Sage, or at least not easily (the
other difficulties such as installation aside). When you install Sage,
it just installs a binary on your computer. You can't type "import
sage" in your regular Python interpreter. You have to run the Sage
Python to get the Sage code.

Third, related to the second point, SymPy is (or at least aims to be)
extensible. So someone should be able to write their own classes that
subclass ours and work nicely with the rest of SymPy without modifying
any SymPy code.

Fourth, specific to group theory, there are places in future code in
other parts of SymPy (e.g., the polys) that could benefit from a
strong group theory module.

Fifth, Sage is GPL, and SymPy is BSD. This won't matter to many
users, but for those for whom it does, it is essential. Examples of
such people might be those people who want to be able to embed the
system into a proprietary system, or simply those people who want to
reuse some of the code in their own project (proprietary or not). I
don't want to start a license war, but it's worth pointing this out,
as it is a real life difference that affects many people.

Aaron Meurer