Java中的置换组实现

Question

根据我在编程方面的经验,我经常面对与排列组相关的不同任务:枚举给定排列的所有可能产品或只计算它们,测试一个排列是否可以表示为给定排列的组合,在给定组中找到一个子组我认为这些问题是计算机科学的经典问题,并且出现在各种编程领域.目前,在我们的项目中,我们使用PermutationGroup基于最简单版本的Schreier-Sims算法的原始实现,但它非常有限.我了解各种C++和Python库,但是有没有任何Java库可以有效地实现PermutationGroup相关主题？

谢谢,斯坦尼斯拉夫.

Answer 1

RedberryPermutationGroup计算机代数系统中有 Java 实现和相关算法（可从Maven Central获取）。它包括在计算机中表示排列群的基本算法（基于基生成集和强生成集以及Schreier-Sims算法）和某些类型的子群（集合稳定器、集中器等）的回溯搜索算法。该实现提供了所有请求的功能：枚举组元素、成员资格测试、组顺序计算（排列总数）等等。cc.redberry.core

以下示例取自 Redbery JavaDoc 页面，重点介绍了一些PermutationGroup功能：

//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());    

有关功能的更多PermutationGroup信息，请参阅Redberry JavaDoc 页面。

还有一个很好的 Java 类 Groovy 接口，可以在此处找到示例。