GSoC 2011 Application Saptarshi Mandal: Combinatorics package for Sympy - sympy/sympy GitHub Wiki
Title: SymPy: Writing a combinatorics package for sympy Student: Saptarshi Mandal Abstract: Sympy currently has little support for combinatorial algorithms found in such packages such as Combinatorica. I plan on implementing and maintaining such a package for Sympy.
Name: Saptarshi Mandal
Email: [email protected]
IRC: saptman on freenode
Phone: Will give to mentor if asked
My Soc proposal is to implement some algorithms of Combinatorica in SymPy.
The algorithms provided in combinatorica have wide applications in fields such as information theory, theoretical computer science, cryptography and networks. Mathematica has arguably, the best implementation of a suite of combinatorial tools [0]. Sage maintains a page indicating what aspects of Combinatorica it has implemented [1]. Currently most of the algorithms presented in these packages are unimplemented in Sympy. The primary issue is the vast size of the implemented methods, many of which rely on non-trivial algorithms, which necessitates prudence in the choice of the techniques one wishes to implement.
I will be developing against the list of algorithms published in [0]. There, the algorithms are divided into 5 categories, a)Subsets and Permutations, b)Partitions and Compositions, c)Graph Construction and Representations, d)Graph Properties and e)Graph Algorithms. I do not plan on implementing the last 3 categories as their functionality is covered in packages such as pygraph and networkx. Instead I will implement algorithms to generate all trees instead. Visualization of these trees will be provided using pygraphviz.
Next I will implement some functionality of the computational group theory package in Mathematica.
Most of the algorithms required to implement the functionality covered in (a) and (b) are described in TAOCP Vol 4. Wherever possible (time permitting obviously) I will implement a few variations of these algorithms. For example, random permutations can be generated both by the original Fisher Yates as well as Durstenfeld's variant. I will implement both and give the user the option of using the one he wants. I can refer to other material as well such as coursework or lecture notes posted on several university websites. The above will require comprehensive usage of Python's functional features and as such will afford me a chance to apply functional programming idioms for solving them.
I plan on roughly following the given schedule but uncertainty will always be there. I will however be in touch with my mentor(s) at all time.
I have been developing an integral equation solver for the past few months which have helped me learn Python and Sympy simultaneously. It mimics the functionality of intsolve in Maple and I hope to get it pushed in soon so that I will have a significant contribution to Sympy before I begin. I have a working knowledge of git. I have already begun prelim work on my project and intend to push some code onto my development branch.
I have pushed some patches for the matrix module and ode module as well.
- Week 1 [Permutations]: I will begin work on the permutations feature. Algorithms for generating all permutations have been given in TAOCP. The stock permutations command will also have options for permutations of n things with k cycles as well as permutations of n items with k runs. I will also implement lexicographic ordering of the permutations as well as other other features like generating derangements and involutions. Other features such as depicting the graph of a permutation can be done later when the graph module is ready. Algorithms for ranking and unranking of permutations have been described in TAOCP which I can implement. Creating an inversion of a permutation has also been discussed.
- Week 2 [Subsets]: Again many of these algorithms have been described in TAOCP. Apart from implementing techniques to generate all subsets including simply the generation of k-subsets of an n set I will also implement methods to enumerate subsets using Gray Code and binary representation. Lexicographic ordering subsets will involve some introspection. For example, if the set is of polynomials, ranking it would involve finding its degree which will depend directly on the polys module.
- Week 3 [Integer]: Implementing integer partitions will also be quite straightforward. Apart from listing all possible partitions I will also implement listing partitions of n whose largest part is k as well as all k-partitions of n. I will also implement Ferrers Diagram, which is a way to visualize a partition. Apart from TAOCP I will also refer to [5].
- Week 4 [Set]: I expect this component to be developed in much the same fashion as the previous ones. Apart from generating all set partitions, k-set partitions and random partitions I can also implement algorithms for ranking and unranking of these partitions..
- Week 5 [Trees]: I intend on implementing algorithms to generate all nested parenthesis of strings as well as all binary trees. I also intend on providing visualization capabilities using pygraphviz. This will be done in week 6. Ranking and unranking algorithms have been covered in TAOCP fasc 4.
- Week 6 [Trees]: This week I intend on implementing algorithms to generate all spanning trees of a given graph. The algorithm for this depends on the set partitions module that I will have written during week 4. I intend on providing the basic infrastructure for graph manipulation using networkx. Networkx interfaces with graphviz as well so visualization is a matter of a few API calls.
- Week 7 [Permutation]: Implementing permutation groups will be a bit tricky as I will need to revise my notes for my Abstract Algebra course. My primary reference for this will be [7]. Most of my time will be taken up in implementing the Schreier-Sims algorithm whose implementation details can be found in [8]. After I am done with this I can write code for generating cyclic groups and dihedral groups. Generating the group of automorphisms of a graph will be implemented later.
- Week 8: Implement algorithms for action on a point, multiplication. I will also write generators for some commonly used groups such as the symmetric group Sn, the alternating group An, the cyclic group Cn and generators for the dihedral group D2n of order 2n.
- Week 9: Implement algorithms for computing orbits, centralizers and stabilizers. These algorithms have been covered in [7] but I can also refer to the lecture notes published in the computational group theory group at Colorado State University.
- Week 10 - 11: Implement Schreier Sims algorithm using the strategy defined below. Once this is done computing the order of a group, testing for membership is done really rapidly.
- Week 12: Polish the code, fix tests and docstrings.
Our aim is to look at permutations of numbers from 1 to n. This can be generalized later. We can represent a permutation as arrays such as below (1 2 3 4 5 6 7) (2 3 1 5 6 4 7) However for larger sized groups its easier to list cycles (1 2 3)(4 5 6)(7) The above encompasses both the above permutations. (1 2 3) are cycled within themselves as are (4 5 6). Only 7 remains in one place. Now if we have a permutation we want to determine all about the group it generates, how big is it, if a given permutation is a member of it and so on. One very famous example is that of a Rubik's cube. The state of a Rubik's cube can be expressed as an element of a permutation group. By finding out if some permutation can be generated by that group we can determine if the Rubik's cube can achieve the state as described by that permutation.
The first module I will implement is simply the PermutationGroups module which will define the group structure on permutations. It will have functionality allowing it to construct a permutation from a list of cycles, order of a permutation and generators for symmetric groups, cyclic groups and dihedral groups. To do this effectively I will need to define a data structure that will allow me to find the order of the group, list its elements without repetition, test for membership and store the elements efficiently. Normally a base and a generating set are quite computationally efficient representations. Algorithms for these tasks have been described in [7]. After this I will implement the deterministic version of Schreier-Sims algorithm which calculates a base and strong generating set of a (permutation) group. To state more formally: Given a group G acting on a finite X, along with a partial base B and partial strong generating set S, show that B is a complete base and S is is a strong generating set or extend B and S so that they are. Now normally a group is given in the form of a generating set. An algorithm to convert this input into a partial base B and a partial strong generating set S has also been given in [7]. With this information we can proceed with the Schreier-Sims algorithm.
Some further notes regarding Permutation Groups implementation https://github.com/sympy/sympy/wiki/Some-notes-regarding-Permutation-Groups
Apart from Combinatorica and Sage, maple has the combinat library. Where Mathematica really shines though is their graph visualization tools. For graph visualization, it seems that graphviz is a good choice. It is a mature library and offers a vast selection of algorithms to display graphs and has several Python bindings. GAP is a CAS with support for computational group theoretic algorithms.
I am a final year student at IIT Kharagpur majoring in Mathematics and Computing. I have taken courses in Real, Complex and Functional Analysis as well as Abstract Algebra, Number Theory and Graph Theory.
I have taken several programming courses as well and am an ardent fan of Haskell and F#. I have solved some Project Euler problems in F#. I do not particularly like Java or C++ but I have done a significant amount of programming in them. This is my first foray into an open source project and so far it has been quite fun. Last summer I interned in Germany under Prof Michael Bohm in the University of Bremen where I worked on Sobolev spaces and PDE theory. Before that I worked under Prog Rajasekhar in my department on applications of Greens function for solving pdes as well as boundary element methods.
I do not have any plans for the summer as I will be graduating and will be at home. I had planned a month long vacation which I will cut down to 3-4 days if I get selected.
My github account's URL is http://github.com/saptman. The relevant branches are dev_ide and combinatorics. Communicating on IRC is a bit problematic for now because of the time difference. I reply to any email as soon as I can though.
[0] http://reference.wolfram.com/mathematica/Combinatorica/guide/CombinatoricaPackage.html
[1] wiki.sagemath.org/CombinatoricaCompare
[2] TAOCP Vol 4, Donald Knuth
[3] Spectral Graph Theory, Fan Chung
[4] Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica, Pemmaraju and Skiena
[5] Fast algorithms for generating integer partitions, Zoghbi et al., Intern. J. Computer Math, Vol 70, pp 319-332
[6] A Fast algorithm for generating set partitions, M. C. Er, The Computer Journal, Vol 31, No. 3
[7] Permutation group algorithms, Akos Seress
[8] Implementation of 3 types of Schreier-Sims Algorithm, Martin Jaggi, MAS334 Project, QMU London