In my experience in programming, I often face with different tasks related to permutation group: enumerate all possible products of given permutations or just count them, test whether one permutation can be represented as a combination of given ones, find a subgroup in a given group etc. I suppose that these problems are classic of a computer science and arise in various fields of programming. Currently, in our project we use our own primitive implementation of PermutationGroup based on a simplest version of Schreier-Sims algorithm, but it is very limited. I know about various C++ and Python libraries, but is there any Java library which have an efficient implementation of PermutationGroup and related topics?
Thanks, Stanislav.
There is implementation of PermutationGroup and related algorithms in Java in Redberry computer algebra system (which is available from Maven Central as cc.redberry.core). It includes basic algorithms for representing permutation groups in computer (based on base and strong generating set and Schreier-Sims algorithm) and backtrack search algorithms for some types of subgroups (set stabilizers, centralizers etc.). The implementation provides all requested features: enumerating group elements, membership testing, calculation of group order (total number of permutations) and many more.
The following example taken from Redbery JavaDoc page highlights some PermutationGroup functionality:
//permutation in cycle notation
Permutation p1 = Permutations.createPermutation(new int[][]{{0, 9, 3}, {5, 8, 6}, {7, 11, 12}});
//permutation in one-line notation
Permutation p2 = Permutations.createPermutation(2, 0, 1, 8, 3, 5, 7, 11, 4, 12, 9, 6, 10);
//Construct permutation group
PermutationGroup pg = PermutationGroup.createPermutationGroup(p1, p2);
//this group is transitive
assert pg.isTransitive();
//its order = 5616
System.out.println(pg.order());
//Create alternating group Alt(13)
PermutationGroup alt13 = PermutationGroup.alternatingGroup(13);
//its order = 3113510400
System.out.println(alt13.order());
assert alt13.containsSubgroup(pg);
//Direct product of two groups
PermutationGroup pp = pg.directProduct(PermutationGroup.symmetricGroup(8));
//Setwise stabilizer
PermutationGroup sw = pp.setwiseStabilizer(1, 2, 3, 9, 10, 11, 12, 3, 14, 15, 16, 17, 18);
assert pp.containsSubgroup(sw);
//its order = 17280
System.out.println(sw.order());
//Center of this stabilizer
PermutationGroup center = sw.center();
//it is abelian group
assert center.isAbelian();
//generators of center
//[+{}, +{{19, 20}}, +{{2, 10}, {3, 9}, {6, 8}, {11, 12}}]
System.out.println(center.generators());
More about PermutationGroup functionality can be found at Redberry JavaDoc page.
There is also a nice Groovy interface to Java classes, examples can be found here.