Help reviewing algorithms for permutation groups

[Aleksandar Makelov]

Hi all,

Time flies and my work on computational group theory is not yet being merged to sympy, so I'm starting to get worried.

So, would anyone enjoy reviewing some of it? I currently have the following publicly available code: one open pull request located here: https://github.com/sympy/sympy/pull/1319
and some more code waiting on my local branch week2: https://github.com/amakelov/sympy/tree/week2

Also, there is an implementation of a randomized Schreier-Sims algorithm along with some other minor additions (see here: http://amakelov.wordpress.com/2012/06/10/google-summer-of-code-2012-week-3/ ) which is not yet pushed to my fork, if anyone's interested.

The main resource I'm using is
Holt, D., Eick, B., O’Brien, E. “Handbook of computational group theory”

If you're working on something that requires some nontrivial mathematical background for review, I'd be happy to help you in turn. :)

[David Joyner]

On Fri, Jun 15, 2012 at 9:06 AM, Aleksandar Makelov
<amak...@college.harvard.edu> wrote:
> Hi all,
>
> Time flies and my work on computational group theory is not yet being merged
> to sympy, so I'm starting to get worried.
>
> So, would anyone enjoy reviewing some of it? I currently have the following

I'd be happy to help but I am not sure what is involved in a review.
I can get the code, read the code, and run tests.
What is involved in a review? Just sign in to github and post a comment
"positive review"?

> publicly available code: one open pull request located here:
> https://github.com/sympy/sympy/pull/1319
> and some more code waiting on my local branch week2:
> https://github.com/amakelov/sympy/tree/week2
>
> Also, there is an implementation of a randomized Schreier-Sims algorithm
> along with some other minor additions (see here:
> http://amakelov.wordpress.com/2012/06/10/google-summer-of-code-2012-week-3/
> ) which is not yet pushed to my fork, if anyone's interested.
>
> The main resource I'm using is
> Holt, D., Eick, B., O’Brien, E. “Handbook of computational group theory”
>
> If you're working on something that requires some nontrivial mathematical
> background for review, I'd be happy to help you in turn. :)
>
>

> --
> 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/-/bdG8bZGxsw0J.
> 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.

[Matthew Rocklin]

Sign up for github. 

Go to this page https://github.com/sympy/sympy/pull/1319

Join the discussion at the bottom

Press the "Diff" button at the top and carefully look through the changes that have been made. You can make comments in line as well (I find this very helpful.)

I actually really like GitHub's interface for code review. I've been toying with the idea of using it in a classroom setting...

[Sergiu Ivanov]

Hello,

On Fri, Jun 15, 2012 at 4:12 PM, David Joyner <wdjo...@gmail.com> wrote:
>
> I'd be happy to help but I am not sure what is involved in a review.
> I can get the code, read the code, and run tests.
> What is involved in a review? Just sign in to github and post a comment
> "positive review"?

That's almost all correct :-)

You should sign in to GitHub and follow one of the links Aleksandar
has provided. There you will be able to view the commits on the
branch from which the pull request has been submitted (you will see a
button Commits). You will also be able to see how the latest version
of the code in the branch looks (Diff page). When you mouse over the
line number in the code view window, you will see a small button which
allow you to post a comment to a certain line of code. Thus,
"reviewing" means commenting on certain pieces of code with the goal
of correcting some mistakes, typos. You will also be able to leave
comments to the whole pull request on the Discussion page.

Sergiu

[David Joyner]

Thanks Matthew and Sergiu for the github help!

I have some general comments and specific comments.

The specific comments all pertain to methods in the permutation
module which I guess were written by someone else and basically
are all questions I have about the docstrings.

The general comment, which is really a design issue
more than anything else, is that I like the module structure laid
out in Sage:
http://www.sagemath.org/doc/reference/groups.html
There is a separate module for all the "named" permutation
groups (eg, the AlternatingGroup), of which there are 16 listed
there. I am afraid that the perm_group module will get too
huge quickly without some thought to a more modular
structure. BTW, I wrote the sage module permgroup_named.py,
http://www.sagemath.org/doc/reference/sage/groups/perm_gps/permgroup_named.html,
and please feel free to take all you want and relicense it BSD
with my permission.

I would also recommend splitting off permutation group homomorphisms,
once you write them, into another module.

About the code you have written, you've done good work on the
documentation. How do I test how the docstrings will
render when they get processed for the sympy manual
http://docs.sympy.org/0.7.1/index.html ? I would like to see how the
html renders, if possible, before making more comments.

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

[Matthew Rocklin]

Checkout his branch on your computer

cd doc

make html

cd _build/html

[David Joyner]

On Fri, Jun 15, 2012 at 10:17 AM, Matthew Rocklin <mroc...@gmail.com> wrote:
> Checkout his branch on your computer
> cd doc
> make html
> cd _build/html

Thanks.
This is taking me some time since I just installed lion on this machine and
make requires a new xcode install. I'm trying to catch up:-)

[Alan Bromborsky]

You might want to install virtual box on you Mac and then install ubuntu
in virtual box and check out the sympy code and doc's that way.

[David Joyner]

On Fri, Jun 15, 2012 at 10:45 AM, Alan Bromborsky <abr...@verizon.net> wrote:

...

>
> You might want to install virtual box on you Mac and then install ubuntu in
> virtual box and check out the sympy code and doc's that way.
>

I switched to a linux box.

How do I download only Aleksandar's clone, with all his code changes
merged as a tarball? I thought github lets me do it but I keep downloading
the wrong tarball.

[Matthew Rocklin]

I switched to a linux box.

+1

 

How do I download only Aleksandar's clone, with all his code changes
merged as a tarball? I thought github lets me do it but I keep downloading
the wrong tarball.

The nicest way is to use git (this also lets you update once he makes changes very easily)

sudo apt-get install git  # if you're using debian/ubuntu

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

git remote add -f his_username git://github.com/his_username/sympy.git

git checkout his_username/branch_name

... play with code

git checkout master # when you're done

and you're good to go. When he makes changes you can run 

git remote update his_username 

git checkout his_username/branch_name

and you'll be all caught up

If you really want a tarball it looks like the following link works

https://github.com/his_username/sympy/tarball/branch_name

[David Joyner]

On Fri, Jun 15, 2012 at 12:03 PM, Matthew Rocklin <mroc...@gmail.com> wrote:
>> I switched to a linux box.
>
> +1
>
>>
>> How do I download only Aleksandar's clone, with all his code changes
>> merged as a tarball? I thought github lets me do it but I keep downloading
>> the wrong tarball.
>
>
> The nicest way is to use git (this also lets you update once he makes
> changes very easily)
>
> sudo apt-get install git  # if you're using debian/ubuntu
> git clone git://github.com/sympy/sympy.git

Thanks! This worked:-)

> git remote add -f his_username git://github.com/his_username/sympy.git

git remote add -f amakelov git://github.com/amakelov/sympy.git

did not work and returned:

"fatal: Not a git repository (or any of the parent directories): .git"

I hve no idea what that means!

> git checkout his_username/branch_name

I tried

git checkout git://github.com/amakelov/sympy.git
and
git checkout git://github.com/amakelov/sympy

but neither worked. I thought the branch name would be
visible from https://github.com/amakelov, but I don't know.

> ... play with code
> git checkout master # when you're done
>
> and you're good to go. When he makes changes you can run
> git remote update his_username
> git checkout his_username/branch_name
>
> and you'll be all caught up
>
>
> If you really want a tarball it looks like the following link works
> https://github.com/his_username/sympy/tarball/branch_name
>

[Matthew Rocklin]

> git remote add -f his_username git://github.com/his_username/sympy.git

git remote add -f amakelov git://github.com/amakelov/sympy.git

did not work and returned:

"fatal: Not a git repository (or any of the parent directories): .git"

I hve no idea what that means!

 

Sorry, I forgot to say that you will need to change into the sympy directory. 

mrocklin@milkweed:~/workspace$ cd sympy

mrocklin@milkweed:~/workspace/sympy$ ls

AUTHORS   data      LICENSE   MANIFEST.in  setup.py  tox.ini.sample

bin       doc       log       README.rst   sympy

build.py  examples  Makefile  setupegg.py  TODO

mrocklin@milkweed:~/workspace/sympy$ git remote add -f amakelov git://github.com/amakelov/sympy.git

Updating amakelov

remote: Counting objects: 46, done.

remote: Compressing objects: 100% (13/13), done.

remote: Total 38 (delta 32), reused 31 (delta 25)

Unpacking objects: 100% (38/38), done.

mrocklin@milkweed:~/workspace/sympy$ git checkout amakelov/week1

[David Joyner]

Thanks Matthew, I got it working - on Lion even.

However, the perm_groups module docstrings are not being
integrated into the reference manual. I don't know how that works.
I added an import statement to the init file, but still no go.
(I'm assuming all the main classes and public functions are supposed
to be imported in sympy by default - is that right?)

Can someone tell me a little on the mechanism of how the
manual gets built?

[Aaron Meurer]

You need to edit the relevant .txt file in doc/src and add them
manually (see the other files for how to do this).

Aaron Meurer

[David Joyner]

On Fri, Jun 15, 2012 at 5:52 PM, Aaron Meurer <asme...@gmail.com> wrote:
> You need to edit the relevant .txt file in doc/src and add them
> manually (see the other files for how to do this).

If the file sympy/doc/src/modules/combinatorics/permutations.txt
is auto-generated from the module permutations.py, then my question is:
How do I get the file perm_groups.py to generate perm_groups.txt?

[Aaron Meurer]

Those files were not autogenerated. They were created manually. 

Aaron Meurer

Sent from my iPad.

[David Joyner]

On Fri, Jun 15, 2012 at 6:14 PM, Aaron Meurer <asme...@gmail.com> wrote:
> Those files were not autogenerated. They were created manually.

Thanks Aaron.

Okay. I added a file perm_group.txt with some obvious text and
modified the combinatorics/index.txt to add that file, then recompiled.
Looks great!

[Aleksandar Makelov]

Thanks a lot David :) Could you send me the contents of the perm_groups.txt file so that I can include it in my amended branch?

>> >>> sympy+unsubscribe@googlegroups.com.

>> >>> For more options, visit this group at
>> >>> http://groups.google.com/group/sympy?hl=en.
>> >>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> >> Groups "sympy" group.
>> >> To post to this group, send email to sy...@googlegroups.com.
>> >> To unsubscribe from this group, send email to

>> >> sympy+unsubscribe@googlegroups.com.

>> >> For more options, visit this group at
>> >> http://groups.google.com/group/sympy?hl=en.
>> >>
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> > Groups "sympy" group.
>> > To post to this group, send email to sy...@googlegroups.com.
>> > To unsubscribe from this group, send email to

>> > sympy+unsubscribe@googlegroups.com.

>> > For more options, visit this group at
>> > http://groups.google.com/group/sympy?hl=en.
>> >
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "sympy" group.
>> To post to this group, send email to sy...@googlegroups.com.
>> To unsubscribe from this group, send email to

>> sympy+unsubscribe@googlegroups.com.

>> For more options, visit this group at
>> http://groups.google.com/group/sympy?hl=en.
>>
>
>
> --
> Sent from my iPad.
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to

> sympy+unsubscribe@googlegroups.com.

[David Joyner]

On Sun, Jun 17, 2012 at 7:09 PM, Aleksandar Makelov
<amak...@college.harvard.edu> wrote:
> Thanks a lot David :) Could you send me the contents of the perm_groups.txt
> file so that I can include it in my amended branch?
>

Done.
(Sent separately, to conserve electrons:-)

> 16 юни 2012, събота, 02:23:31 UTC+3, David Joyner написа:
>>
>> On Fri, Jun 15, 2012 at 6:14 PM, Aaron Meurer <asme...@gmail.com> wrote:
>> > Those files were not autogenerated. They were created manually.
>>
>> Thanks Aaron.
>>
>> Okay. I added a file perm_group.txt with some obvious text and
>> modified the combinatorics/index.txt to add that file, then recompiled.
>> Looks great!

...

> --
> 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/-/cCZrxaYegXQJ.

>
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to

> sympy+un...@googlegroups.com.

[Aaron Meurer]

On Jun 17, 2012, at 5:25 PM, David Joyner <wdjo...@gmail.com> wrote:

> On Sun, Jun 17, 2012 at 7:09 PM, Aleksandar Makelov
> <amak...@college.harvard.edu> wrote:
>> Thanks a lot David :) Could you send me the contents of the perm_groups.txt
>> file so that I can include it in my amended branch?
>>
>
> Done.
> (Sent separately, to conserve electrons:-)

By the way. The best way to do this is if you push it up to a branch
and he merges it. This makes things much easier, and it also preserved
the commit authorship.

Aaron Meurer

[Aleksandar Makelov]

15 юни 2012, петък, 17:07:44 UTC+3, David Joyner написа:

Thanks Matthew and Sergiu for the github help!

I have some general comments and specific comments.

The specific comments all pertain to methods in the permutation
module which I guess were written by someone else and basically
are all questions I have about the docstrings.

The general comment, which is really a design issue
more than anything else, is that I like the module structure laid
out in Sage:
http://www.sagemath.org/doc/reference/groups.html
There is a separate module for all the "named" permutation
groups (eg, the AlternatingGroup), of which there are 16 listed
there. I am afraid that the perm_group module will get too
huge quickly without some thought to a more modular
structure. BTW, I wrote the sage module permgroup_named.py,
http://www.sagemath.org/doc/reference/sage/groups/perm_gps/permgroup_named.html,
and please feel free to take all you want and relicense it BSD
with my permission.

Good, this is now addressed in my pull request for weeks 2-3: https://github.com/sympy/sympy/pull/1377

> To unsubscribe from this group, send email to sympy+unsubscribe@googlegroups.com.

[David Joyner]

On Sat, Jun 23, 2012 at 10:59 AM, Aleksandar Makelov
<amak...@college.harvard.edu> wrote:
>
>

...

>> The general comment, which is really a design issue
>> more than anything else, is that I like the module structure laid
>> out in Sage:
>> http://www.sagemath.org/doc/reference/groups.html
>> There is a separate module for all the "named" permutation
>> groups (eg, the AlternatingGroup), of which there are 16 listed
>> there. I am afraid that the perm_group module will get too
>> huge quickly without some thought to a more modular
>> structure. BTW, I wrote the sage module permgroup_named.py,
>>
>> http://www.sagemath.org/doc/reference/sage/groups/perm_gps/permgroup_named.html,
>> and please feel free to take all you want and relicense it BSD
>> with my permission.
>
>
> Good, this is now addressed in my pull request for weeks 2-3:
> https://github.com/sympy/sympy/pull/1377

Great work. Looks like good progress to me.

When trying to implement the Rubik's cube group for testing, I ran
into the following


g1 = Permutation([[1, 3, 8, 6],[2, 5, 7,
4],[9,33,25,17],[10,34,26,18],[11,35,27,19]])
---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
/Users/wdj/pythonfiles/sympy/<ipython-input-6-08f78f951d6f> in <module>()
----> 1 g1 = Permutation([[1, 3, 8, 6],[2, 5, 7,
4],[9,33,25,17],[10,34,26,18],[11,35,27,19]])

/Users/wdj/pythonfiles/sympy/sympy/combinatorics/permutations.py in
__new__(cls, *args, **kw_args)
365 temp = [int(i) for i in flatten(args[0])]
366 if set(range(len(temp))) != set(temp):
--> 367 raise ValueError("Integers 0 through %s must be
present." % len(temp))
368
369 cform = aform = None

ValueError: Integers 0 through 20 must be present.



I assume this is because disjoint cycle notation is not yet completely
implemented?

>>
>>
>> I would also recommend splitting off permutation group homomorphisms,
>> once you write them, into another module.

...

>
> --
> 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/-/km-fcZm_MskJ.

>
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to

> sympy+un...@googlegroups.com.

[Aleksandar Makelov]

Yes, cyclic notation is available, but at present you have to list all the fixed points as well, which is sort of ugly. Using the occasion to talk about it,
I intend to do the following to deal with it:
- when a permutation is entered in cyclic form, find the maximum of the numbers present and set the degree of the permutation to be this maximum + 1
- supply an additional argument to the constructor so that the degree can be set manually (for example, Perm([[0,1]], 1000) )
This is going to lead to some complications, for example when multiplying two permutations with different degrees, and so on and so on... but still seems reasonable.
What do you guys think about this idea, and do you have any other suggestions for a possible way to exclude the singleton cycles from the cyclic form?

>>
>>
>> I would also recommend splitting off permutation group homomorphisms,
>> once you write them, into another module.

...

>
> --
> 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/-/km-fcZm_MskJ.
>
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to

> sympy+unsubscribe@googlegroups.com.

[David Joyner]

On Sat, Jun 23, 2012 at 1:20 PM, Aleksandar Makelov
<amak...@college.harvard.edu> wrote:
>
>

...

>

> Yes, cyclic notation is available, but at present you have to list all the
> fixed points as well, which is sort of ugly. Using the occasion to talk
> about it,
> I intend to do the following to deal with it:
> - when a permutation is entered in cyclic form, find the maximum of the
> numbers present and set the degree of the permutation to be this maximum + 1
> - supply an additional argument to the constructor so that the degree can be
> set manually (for example, Perm([[0,1]], 1000) )

This seems like a good solution. This would imply, if I understand your idea,
SymmetricGroup(100).has_element(Perm([[0,1]], 1000)) is True
SymmetricGroup(100).has_element(Perm([[0,1]])) is False.
Right?

> This is going to lead to some complications, for example when multiplying
> two permutations with different degrees, and so on and so on... but still
> seems reasonable.
> What do you guys think about this idea, and do you have any other
> suggestions for a possible way to exclude the singleton cycles from the
> cyclic form?

The way I dealt with it in sage was to assume everything is in
disjoint cycle notation (dcn),
by default, and to write converter functions when the array or list
notation was more useful.
For example, the list notation is useful if you want to compute the
permutation matrix.

I guess you could just as easily assume everything is in list notation
by default.
I don't see an "action" method in permutations.py, where p.action(i) returns j,
where p is a permutation and i, are elements from 0 to degree(p)-1 and
p sends i to j when i is fed into p from the left. I am probably
missing it. Anyway,
once you have that method, it is easy to write a dsn to list notation converter.
You can test the input syntax (see if integers are missing or if the structure
of the permutation is a list of lists), and convert to list notation if needed.

>>
>> >>
>> >>
>> >> I would also recommend splitting off permutation group homomorphisms,
>> >> once you write them, into another module.
>>
>> ...
>>
>> >
>> > --
>> > 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/-/km-fcZm_MskJ.
>> >
>> > 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.
>

> --
> 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/-/2YWTz4zi7WEJ.

>
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to

> sympy+un...@googlegroups.com.

[krastano...@gmail.com]

Is Perm a Basic object? If so, you should get acquainted with the
requirements about obj.func(*obj.args)==obj. Is it tested in
test_args.py? If it is not a Basic object, why not?

I am asking all this, because it may interfere with your decision to
use some parameters in the constructor.

You should also ensure that you have consistent hash values?

Does the following work

>>> a = Perm(some_arguments)
>>> b = Perm(the_same_arguments)
>>> a == b
True I presume
>>> hash(a) == hash(b)
True I hope
>>> id(a) == id(b)
False most probably, unless caching works really well