CayleyR：通过循环交叉解决TopSpin谜题

# CayleyR：通过循环相交解决TopSpin谜题
来源：https://arxiv.org/html/2607.13219

###### 摘要

本文介绍cayleyR，一个用于通过检测Cayley图中循环相交来解决排列谜题的R包。核心算法执行迭代双向搜索：从初始和目标排列状态出发，随机操作序列在对称群SnS_{n}Cayley图中生成循环；它们的相交产生一条连接路径。当未发现直接相交时，基于距离的桥接选择缩小差距，并重复该过程。该包针对TopSpin(n,k)(n,k)谜题，其状态空间是由循环移位和前缀逆转生成的SnS_{n}Cayley图。我们描述了数学框架、算法及其实现，该实现结合了C++哈希索引状态存储和可选的Vulkan GPU加速。该软件可在CRAN上公开获取。

###### 2020数学主题分类：
主类20B40；次类05C25, 68W05

## 1. 引言

TopSpin谜题由排放在圆形轨道上的n个令牌和一个宽度为k的旋转门窗口组成。每一步有两种操作：(i) 整个轨道向左或向右循环移位一个位置，以及 (ii) 逆转当前在旋转门内的k个令牌。目标是通过有限序列的此类操作将给定的令牌排列转换为目标排列。

代数上，每个排列对应对称群SnS_{n}中的一个元素，两个移位方向和逆转定义了三个生成元，所有可达排列的集合构成Cayley图Γ(Sn,{L,R,X})\Gamma(S_{n},\{L,R,X\})。当k为偶数时，生成的群是整个SnS_{n}；当k为奇数时，则为交错群AnA_{n}。求解谜题等价于在Γ\Gamma中寻找两个顶点之间的路径。

对于较小的n，穷举广度优先搜索（BFS）是可行的：SnS_{n}的Cayley图有n!个顶点，因此BFS仅在实际可行范围内约n≤10。超过此阈值，状态空间呈超指数增长，经典最短路径算法变得难以处理。TopSpin Cayley图的直径被推测为Θ(n2)\Theta(n^{2})[4 (https://arxiv.org/html/2607.13219#bib.bib4)]，进一步加剧了难度。

在本文中，我们提出一种根本不同的策略。我们不逐层探索图，而是从起始和目标状态生成随机循环，并在这两组循环之间搜索相交。当检测到共享状态时，通过将每个循环链追溯回其起点来立即恢复路径。当一轮采样后不存在相交时，算法选择一对桥状态——每边一个，选择以最小化距离启发式——并从这些桥重新开始循环生成。这种迭代与桥接方案在两条扩展前沿相遇时终止。

主要贡献如下：

1. (1)我们引入了用于在置换群Cayley图中寻路的迭代循环相交（ICI）算法（第4节 (https://arxiv.org/html/2607.13219#S4)）。
2. (2)我们描述了cayleyR，一个实现此算法的开源R包，带有C++后端、哈希索引状态存储和可选的Vulkan GPU加速（第5节 (https://arxiv.org/html/2607.13219#S5)）。
3. (3)我们报告了计算实验，展示了该方法在n高达20的TopSpin(n,k)(n,k)实例上的可扩展性（第6节 (https://arxiv.org/html/2607.13219#S6)）。

本文其余部分组织如下。第2节 (https://arxiv.org/html/2607.13219#S2)回顾必要的代数和图论预备知识。第3节 (https://arxiv.org/html/2607.13219#S3)调查相关工作。第4节 (https://arxiv.org/html/2607.13219#S4)和第5节 (https://arxiv.org/html/2607.13219#S5)包含主要的算法和软件贡献。第6节 (https://arxiv.org/html/2607.13219#S6)介绍实验，第8节 (https://arxiv.org/html/2607.13219#S8)总结。

## 2. 预备知识

###### 定义 1（Cayley图）.

设GG为群，S⊆GS\subseteq G为生成集且e∉Se\notin S。Cayley图Γ(G,S)\Gamma(G,S)是以GG为顶点集的有向图，对于每个g∈Gg\in G和s∈Ss\in S，从gg到gsgs有一条边。如果SS对逆封闭，则该图是无向的。

###### 定义 2（TopSpin(n,k)(n,k)谜题）.

固定整数n≥3n\geq 3和2≤k≤n2\leq k\leq n。状态空间是{1,…,n}\{1,\dots,n\}的所有排列的集合，与SnS_{n}的元素等同。三个生成元作用于状态σ=(σ1,…,σn)\sigma=(\sigma_{1},\dots,\sigma_{n})：

(1)L(σ)\displaystyle L(\sigma)=(σ2,σ3,…,σn,σ1),\displaystyle=(\sigma_{2},\sigma_{3},\dots,\sigma_{n},\sigma_{1}),(2)R(σ)\displaystyle R(\sigma)=(σn,σ1,σ2,…,σn−1),\displaystyle=(\sigma_{n},\sigma_{1},\sigma_{2},\dots,\sigma_{n-1}),(3)Xk(σ)\displaystyle X_{k}(\sigma)=(σk,σk−1,…,σ1,σk+1,…,σn).\displaystyle=(\sigma_{k},\sigma_{k-1},\dots,\sigma_{1},\sigma_{k+1},\dots,\sigma_{n}).注意R=L−1R=L^{-1}且Xk=Xk−1X_{k}=X_{k}^{-1}。TopSpin Cayley图是Γ(G,{L,R,Xk})\Gamma(G,\{L,R,X_{k}\})，其中若k为偶数则G=SnG=S_{n}，若k为奇数则G=AnG=A_{n}。

###### 定义 3（操作序列的循环）.

设w=(w1,…,wm)w=(w_{1},\dots,w_{m})为字母表{L,R,Xk}\{L,R,X_{k}\}上的有限词，并令φw=wm∘⋯∘w1\varphi_{w}=w_{m}\circ\cdots\circ w_{1}表示复合置换。从状态σ0\sigma_{0}出发，ww在σ0\sigma_{0}处的循环是序列

σ0,φw(σ0),φw2(σ0),…,φwc−1(σ0),\sigma_{0},\;\varphi_{w}(\sigma_{0}),\;\varphi_{w}^{2}(\sigma_{0}),\;\dots,\;\varphi_{w}^{c-1}(\sigma_{0}),其中c=ord(φw)c=\mathrm{ord}(\varphi_{w})是φw\varphi_{w}在GG中的阶，即满足φwc=e\varphi_{w}^{c}=e的最小正整数。整数cc称为循环长度。由于GG是有限的，该序列是周期性的，并在恰好c次应用φw\varphi_{w}后返回σ0\sigma_{0}。

###### 定义 5（距离函数）.

对于两个排列σ,τ∈Sn\sigma,\tau\in S_{n}，我们使用两种距离启发式。

- •曼哈顿距离：dM(σ,τ)=∑i=1n|σi−τi|d_{M}(\sigma,\tau)=\sum_{i=1}^{n}|\sigma_{i}-\tau_{i}|。
- •断点距离：令π=τ−1σ\pi=\tau^{-1}\sigma为相对排列，并用哨兵π0=0\pi_{0}=0和πn+1=n+1\pi_{n+1}=n+1扩展。则dB(σ,τ)=#{i∈{0,…,n}:|πi+1−πi|>1}d_{B}(\sigma,\tau)=\#\{i\in\{0,\dots,n\}:|\pi_{i+1}-\pi_{i}|>1\}。

## 3. 相关工作

排列谜题与Cayley图。排列谜题与Cayley图之间的联系是经典的：每个谜题状态是一个顶点，每个合法操作是一条由生成元标记的边。广义(n2−1)(n^{2}-1)谜题被Ratner和Warmuth证明为NP难[9 (https://arxiv.org/html/2607.13219#bib.bib9)]。专门针对TopSpin谜题，群论结构——特别是给定n和k时哪些排列可达——已在[7 (https://arxiv.org/html/2607.13219#bib.bib7),10 (https://arxiv.org/html/2607.13219#bib.bib10)]中分析。标准TopSpin(20,4)(20,4)谜题有20!个状态，当k=4时生成整个对称群S20S_{20}，这是众所周知的。

最优求解与模式数据库。Bortoluzzi[1 (https://arxiv.org/html/2607.13219#bib.bib1)]开发了一个针对TopSpin的领域特定求解器，使用模式数据库启发式结合IDA*。通过预计算抽象子问题中的距离，模式数据库提供了可接受的启发式，极大地剪枝搜索树。然而，该方法受限于数据库的指数增长：即使是中等模式大小（3-6个令牌）也需要大量内存和预计算时间，并且扩展到n=9以上变得困难。

直径与距离问题。TopSpin Cayley图Γ(Sn,{L,R,Xk})\Gamma(S_{n},\{L,R,X_{k}\})的直径被推测为Θ(n2)\Theta(n^{2})。Chervov和Soibelman[4 (https://arxiv.org/html/2607.13219#bib.bib4)]研究了密切相关的LRX Cayley图，并推测其直径为n(n−1)/2n(n-1)/2。在后续工作中，Chervov等人[5 (https://arxiv.org/html/2607.13219#bib.bib5)]提出了SnS_{n}Cayley图的全息对偶框架，将顶点映射到平面多边形内的格路，词度量对应路下的面积；这将直径计算与Ehrhart拟多项式联系起来，并为排列距离提供了几何视角。

大规模状态空间的搜索算法。双向BFS是标准技术，将搜索前沿从O(bd)O(b^{d})减少到O(bd/2)O(b^{d/2})，其中b是分支因子，d是解深度。对于非常大的状态空间，随机化方法变得有吸引力：Cayley图上的随机游走已在混合时间[6 (https://arxiv.org/html/2607.13219#bib.bib6)]以及关于单群Cayley图直径的Babai猜想的背景下得到广泛研究。

本文的方法。本文的循环相交策略在几个方面与上述方法不同。与BFS或IDA*不同，它不逐层探索图，也不保证最短路径。与模式数据库不同，它不需要预计算，也不需要内存密集型的查找表。与随机游走方法不同，它不依赖混合性质，而是利用循环的代数结构——复合置换φw\varphi_{w}具有有限阶，其迭代系统地覆盖状态空间的大片区域。最接近的类似物是中间相遇范式，但这里的“相遇深度”不是先验固定的；相反，它通过循环相交和迭代桥选择动态发现。

## 4. 迭代循环相交算法

现在我们描述cayleyR中实现的主要算法。输入是Cayley图Γ(G,{L,R,Xk})\Gamma(G,\{L,R,X_{k}\})中的一对状态σs\sigma_{s}（起始）和σf\sigma_{f}（目标），输出是一个将σs\sigma_{s}变换为σf\sigma_{f}的生成元序列。

### 4.1 概述

该算法维护两个状态存储S\mathcal{S}和F\mathcal{F}，分别从σs\sigma_{s}和σf\sigma_{f}扩展。每次迭代（称为一轮循环扩展）包含四个阶段：

1. (1)随机组合生成。在字母表{L,R,Xk}\{L,R,X_{k}\}上生成一批指定长度ℓ\ell的随机操作序列w(1),…,w(N)w^{(1)},\dots,w^{(N)}。在每个序列上，在当前种子状态评估以确定其循环长度（定义3 (https://arxiv.org/html/2607.13219#Thmtheorem3)）。排名靠前的序列——按循环长度、唯一状态数或其他标准排序——被保留。
2. (2)循环扩展。对于每个保留的序列w(j)w^{(j)}，展开整个循环：计算所有中间状态，并将其插入到相应的状态存储（S\mathcal{S}或F\mathcal{F}）中，同时附带元数据（步骤索引、组合索引、循环编号、操作标签）。
3. (3)相交检查。算法使用哈希索引查找查询S∩F≠∅\mathcal{S}\cap\mathcal{F}\neq\varnothing。如果找到相交状态σ∗\sigma^{*}，则重建路径（第4.2节 (https://arxiv.org/html/2607.13219#S4.SS2)）并终止算法。
4. (4)桥选择。如果未找到相交，则从每边选择一个桥状态。令US=unique(S)\mathcal{U}_{\mathcal{S}}=\mathrm{unique}(\mathcal{S})和UF=unique(F)\mathcal{U}_{\mathcal{F}}=\mathrm{unique}(\mathcal{F})。关键思想是每个前沿搜索靠近相反端点的状态：US\mathcal{U}_{\mathcal{S}}中的状态（从起始扩展而来）按到σf\sigma_{f}的距离排序，而UF\mathcal{U}_{\mathcal{F}}中的状态（从目标扩展而来）按到σs\sigma_{s}的距离排序。这一对称标准驱动两个前沿相互靠近。从每边最近的10个状态中，随机均匀选择一个。这两个状态成为下一轮的种子状态。

重复该过程，直到找到相交或达到最大迭代次数。

算法 1 迭代循环相交 (ICI)

输入：状态σs,σf∈G\sigma_{s},\sigma_{f}\in G；旋转门宽度kk；操作{L,R,Xk}\{L,R,X_{k}\；组合长度ℓ\ell；样本数NN；顶部计数NtopN_{\mathrm{top}}；最大迭代次数TT；距离函数dd。

输出：操作序列PP，使得P(σs)=σfP(\sigma_{s})=\sigma_{f}，或失败。

1:
S←CreateStore()\mathcal{S}\leftarrow\texttt{CreateStore}();
F←CreateStore()\mathcal{F}\leftarrow\texttt{CreateStore}()
2:
βs←σs\beta_{s}\leftarrow\sigma_{s};
βf←σf\beta_{f}\leftarrow\sigma_{f}{当前种子状态}
3:
Bs←[(σs,0)]B_{s}\leftarrow[(\sigma_{s},0)];
Bf←[(σf,0)]B_{f}\leftarrow[(\sigma_{f},0)]{桥状态历史}
4:for
t=1t=1toTTdo
5:{— 前向扩展 —}
6:
Ws←SampleCombos(ℓ,N)W_{s}\leftarrow\texttt{SampleCombos}(\ell,N)
7:
Ws∗←RankAndFilter(Ws,βs,k,Ntop)W_{s}^{*}\leftarrow\texttt{RankAndFilter}(W_{s},\beta_{s},k,N_{\mathrm{top}})
8:
ExpandCycles(S,Ws∗,βs,k,t)\texttt{ExpandCycles}(\mathcal{S},W_{s}^{*},\beta_{s},k,t)
9:
10:{— 后向扩展 —}
11:
Wf←SampleCombos(ℓ,N)W_{f}\leftarrow\texttt{SampleCombos}(\ell,N)
12:
Wf∗←RankAndFilter(Wf,βf,k,Ntop)W_{f}^{*}\leftarrow\texttt{RankAndFilter}(W_{f},\beta_{f},k,N_{\mathrm{top}})
13:
ExpandCycles(F,Wf∗,βf,k,t)\texttt{ExpandCycles}(\mathcal{F},W_{f}^{*},\beta_{f},k,t)
14:
15:{— 相交检查 —}
16:
I←S∩FI\leftarrow\mathcal{S}\cap\mathcal{F}{基于哈希，O(min⁡(|S|,|F|))O(\min(|\mathcal{S}|,|\mathcal{F}|))}
17:if
I≠∅I\neq\varnothingthen
18:选择
σ∗∈I\sigma^{*}\in I
19:
Ps←ReconstructPath(S,Bs,σ∗)P_{s}\leftarrow\texttt{ReconstructPath}(\mathcal{S},B_{s},\sigma^{*})
20:
Pf←ReconstructPath(F,Bf,σ∗)P_{f}\leftarrow\texttt{ReconstructPath}(\mathcal{F},B_{f},\sigma^{*})
21:返回
Ps⋅Invert(Pf)P_{s}\cdot\texttt{Invert}(P_{f})
22:endif
23:
24:{— 桥选择 —}
25:
US←Unique(S)\mathcal{U}_{\mathcal{S}}\leftarrow\texttt{Unique}(\mathcal{S});
UF←Unique(F)\mathcal{U}_{\mathcal{F}}\leftarrow\texttt{Unique}(\mathcal{F})
26:
Δs←{(τ,d(σf,τ)):τ∈US}\Delta_{s}\leftarrow\{(\tau,d(\sigma_{f},\tau)):\tau\in\mathcal{U}_{\mathcal{S}}\}; 升序排序
27:
Δf←{(τ,d(σs,τ)):τ∈UF}\Delta_{f}\leftarrow\{(\tau,d(\sigma_{s},\tau)):\tau\in\mathcal{U}_{\mathcal{F}}\}; 升序排序
28:
βs←RandomFrom(Top10(Δs))\beta_{s}\leftarrow\texttt{RandomFrom}(\texttt{Top}_{10}(\Delta_{s}))
29:
βf←RandomFrom(Top10(Δf))\beta_{f}\leftarrow\texttt{RandomFrom}(\texttt{Top}_{10}(\Delta_{f}))
30:追加
(βs,t)