Permutation group implementation in Java

Question

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.

Answer 1

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.

Answer 2

Guava's Collections2 have zero-memory implementaion of permutations collections. So you can apply basic collection methods on them or Guava's additional operations in Collections2 and Iterables.

• orderedPermutations(Iterable) - Returns a Collection of all the permutations of the specified Iterable using the specified Comparator for establishing the lexicographical ordering. Notes: This is an implementation of the algorithm for Lexicographical Permutations Generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2. The iteration order follows the lexicographical order. This means that the first permutation will be in ascending order, and the last will be in descending order.
• permutations(Collection) - Returns a Collection of all the permutations of the specified Collection. Notes: This is an implementation of the Plain Changes algorithm for permutations generation, described in Knuth's "The Art of Computer Programming", Volume 4, Chapter 7, Section 7.2.1.2.