Stanislav Poslavsky - 2 years ago 146
Java Question

# Permutation group implementation in Java

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download