寻找树对称性的算法
我有n个扇区，逆时针枚举0到n-1。这些扇区之间的边界是无限的分支（n 个）。 这些扇区位于复平面中，对于 n 偶数， 扇区 0 和 n/2 被实轴平分，扇区间隔均匀。
这些分支在某些点相交，称为交汇点。每个交汇点都与部分扇区（至少 3 个）相邻。
指定交汇点（按照预先确定的顺序，比方说，从与扇区 0 和 1 相邻的交汇点开始）以及交汇点之间的距离，唯一地描述了树。
现在，给定这样的表示，我如何查看它是否相对于实轴对称？
例如，n=6，树 (0,1,5)(1,2,4,5)(2,3,4) 在实线上有 3 个交点， 所以它相对于实轴对称。 如果 (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 或任何其他人类可读的语言就足够了。
（这些对称性对应于薛定谔方程中的特殊势能， 它在量子力学中具有很好的特性。）
I have n sectors, enumerated 0 to n-1 counterclockwise. The boundaries between these sectors are infinite branches (n of them).
The sectors live in the complex plane, and for n even,
sector 0 and n/2 are bisected by the real axis, and the sectors are evenly spaced.
These branches meet at certain points, called junctions. Each junction is adjacent to a subset of the sectors (at least 3 of them).
Specifying the junctions, (in pre-fix order, lets say, starting from junction adjacent to sector 0 and 1), and the distance between the junctions, uniquely describes the tree.
Now, given such a representation, how can I see if it is symmetric wrt the real axis?
For example, n=6, the tree (0,1,5)(1,2,4,5)(2,3,4) have three junctions on the real line,
so it is symmetric wrt the real axis.
If the distances between (015) and (1245) is equal to distance from (1245) to (234),
this is also symmetric wrt the imaginary axis.
The tree (0,1,5)(1,2,5)(2,4,5)(2,3,4) have 4 junctions, and this is never symmetric wrt either imaginary or real axis, but it has 180 degrees rotation symmetry if the distance between the first two and the last two junctions in the representation are equal.
Edit:
Here are all trees with 6 branches, distances 1.
http://www2.math.su.se/~per/files/allTrees.pdf
So, given the description/representation, I want to find some algorithm to decide if it is symmetric wrt real, imaginary, and rotation 180 degrees. The last example have 180 degree symmetry.
Edit 2:
This is actually for my research. I have posted the question at mathoverflow as well,
but my days in competition programming tells me that this is more like an IOI task.
Code in mathematica would be excellent, but java, python, or any other language readable by a human suffices.
(These symmetries corresponds to special kinds of potential in the Schroedinger equation,
which has nice properties in quantum mechanics.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您能更好地定义树的对称性吗？
你先这么说
并且您想要找到对称性
我会期望对称性将是纯粹几何的，但你也说，在对贾斯汀答案的评论中
如果树的顶点位置不能在平面上唯一定义，如何寻找几何对称性？此外，在您给出的许多图中（N=6，甚至）扇区0和3没有被x轴（实轴）一分为二，所以我认为您自己的绘图是错误的。
Could you please define better what you mean by symmetry of the tree?
You first say that
and that you want to find symmetry
I would then expect that the symmetries would be purely geometrical, but then you also say, in the comment to Justin's answer
How can you look for geometrical symmetry if the position of the vertices of the tree cannot be uniquely defined on the plane? Furthermore in many of the plots you have given (N=6, even) sectors 0 and 3 are not bisected by the x axis (real axis), so I would deem your own drawings wrong.
由于您已经有一个算法来构造树的点集，因此您只需要确定点集是否具有翻转对称性。理想情况下，您的集合是针对非有理点进行符号计算的（并以 sin(theta)、cos(theta) 表示），这应该没问题，因为您似乎正在使用 Mathematica。
您现在想知道您的点集是否关于某个轴对称，因此将翻转/旋转变换表示为矩阵 A，我们有 {x'} = A >{x}。对后像集 {x'} 进行排序（使用表达式而不是数值），并与原始点集 {x} 进行比较。如果不存在一一对应关系，那么就没有对称性，否则就有对称性。
我认为有一个mathematica函数可以找到集合中的唯一表达式（例如Unique[beforeImage] == Unique[afterImage]）
Since you already have an algorithm to construct the point set for the tree, you only need to determine if the point set has flip symmetry. Ideally your set is computed symbolically (and left in terms of sin(theta), cos(theta)) for non rational points, which should be fine since you seem to be using Mathematica.
You now want to know if your point set has a symmetry about some axis, so represent the flip/rotation transformation as a matrix A, and we have {x'} = A{x}. Sort the after image set {x'} (using the expressions not the numeric values), and compare to the original point set {x}. If there is not a 1-1 correspondence then you don't have a symmetry otherwise you do.
I think there is a mathematica function to find the unique expressions in a set (e.g. Unique[beforeImage] == Unique[afterImage])
我还没有时间实现这个，也许这里有人可能会更进一步：
首先按象限划分交界处，这应该产生 4 棵树。 { Tpp, Tmp, Tmm, Tpm}（p 为正，m 为负）。现在检查对称性似乎是定向广度优先遍历：
在我的数学上已经有一段时间了，所以这些都不会编译
其中 TraverseCompare 使用沿一棵树的呼吸优先遍历和逆序广度优先来检查树的结构沿着另一棵树遍历。 （类似于以下内容，但这在 处不起作用）。
I have not had time to implement this, perhaps someone here might take it further:
First partition the junctions by quadrant, this should produce 4 trees. { Tpp, Tmp, Tmm, Tpm} (p for plus, m for minus). Now checking for symmetry seems to be a directional breadth first traversal:
Its been a while on my mathematica, so none of this will compile
Where TraverseCompare checks the structure of the tree using a breath first traversal along one tree, and a reverse order breadth first traversal along the other tree. (something like the following, but this won't work at ).