6

在我的编程经验中，我经常面临与排列组相关的不同任务：枚举给定排列的所有可能乘积或只计算它们，测试一个排列是否可以表示为给定排列的组合，在给定组中找到一个子组等等。我想这些问题是计算机科学的经典问题，并且出现在编程的各个领域。目前，在我们的项目中，我们使用我们自己的PermutationGroup基于最简单版本的 Schreier-Sims 算法的原始实现，但它非常有限。我知道各种 C++ 和 Python 库，但是是否有任何 Java 库可以有效地实现PermutationGroup和相关主题？

谢谢，斯坦尼斯拉夫。

4

2 回答 2

3

Redberry计算机代数系统（可从Maven Central获取）中的 Java实现PermutationGroup和相关算法。它包括在计算机中表示置换群的基本算法（基于基础和强生成集以及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 接口，可以在此处找到示例。

于 2014-03-27T20:13:56.063 回答
1

Guava 的Collections2具有排列集合的零内存实现。所以你可以对它们应用基本的收集方法或 Guava 在Collections2和中的附加操作Iterables。

  • orderedPermutations(Iterable)- 使用指定的 Comparator 返回指定 Iterable 的所有排列的集合，以建立字典顺序。注意：这是字典排列生成算法的实现，在 Knuth 的“计算机编程的艺术”，第 4 卷，第 7 章，第 7.2.1.2 节中进行了描述。迭代顺序遵循字典顺序。这意味着第一个排列将按升序排列，最后一个排列将按降序排列。
  • permutations(Collection)- 返回指定集合的​​所有排列的集合。注意：这是用于排列生成的 Plain Changes 算法的实现，在 Knuth 的“计算机编程的艺术”，第 4 卷，第 7 章，第 7.2.1.2 节中进行了描述。
于 2013-10-21T20:51:03.883 回答