Per*_*son 9 algorithm combinatorics
我有n个扇区,逆时针枚举0到n-1.这些扇区之间的边界是无限分支(n个).扇区位于复平面中,对于n even,扇区0和n/2被实轴一分为二,扇区间隔均匀.
这些分支在某些点相遇,称为交叉点.每个交叉点与扇区的子集相邻(至少3个).
指定连接点(以预固定顺序,比如从邻近扇区0和1的连接点开始)以及连接点之间的距离,唯一地描述了树.
现在,给定这样的表示,我怎样才能看到它是否与实轴对称？
例如,n = 6,树(0,1,5)(1,2,4,5)(2,3,4)在实线上有三个结,因此它与实轴对称.如果(015)和(1245)之间的距离等于从(1245)到(234)的距离,则这也与虚轴对称.
树(0,1,5)(1,2,5)(2,4,5)(2,3,4)有4个连接点,这在假想轴或实轴上都不是对称的,但它有180个如果表示中前两个和最后两个结之间的距离相等,则旋转对称度.
编辑:以下是所有树木有6个分支,距离为1. http://www2.math.su.se/~per/files/allTrees.pdf
因此,给定描述/表示,我想找到一些算法来确定它是否是真实的,虚构的和180度旋转的对称.最后一个例子具有180度对称性.
编辑2:这实际上是我的研究.我也在mathoverflow上发布了这个问题,但是我在竞赛编程中的日子告诉我这更像是一个IOI任务.mathematica中的代码非常好,但java,python或人类可读的任何其他语言都足够了.
(这些对称性对应于Schroedinger方程中的特殊种类,它在量子力学中具有很好的性质.)
由于您已经有一个算法来构造树的点集，因此您只需要确定点集是否具有翻转对称性。理想情况下，您的集合是针对非有理点进行符号计算的（并以 sin(theta)、cos(theta) 表示），这应该没问题，因为您似乎正在使用 Mathematica。
您现在想知道您的点集是否关于某个轴对称，因此将翻转/旋转变换表示为矩阵A，并且我们有 {x'} = A {x}。对后像集 {x'} 进行排序（使用表达式而不是数值），并与原始点集 {x} 进行比较。如果不存在一一对应关系，那么就没有对称性，否则就有对称性。
我认为有一个mathematica函数可以找到集合中的唯一表达式（例如Unique[beforeImage] == Unique[afterImage]）