《Discrete Applied Mathematics》：Efficient methods of constructing shorthand universal cycles for permutations
編輯推薦：
本文推薦研究“構造排列縮略通用環的高效方法”（Efficient methods of constructing shorthand universal cycles for permutations）。文章聚焦于一類特殊的通用環（Universal cycles， UC），即排列的縮略通用環（shorthand universal cycles for permutations）。作者提出了三種簡潔高效的構造方法，這些方法基于巧妙設計后續規則（successor rules），尤其第三種方法能生成∏t=2n-2t!個移位不等價的序列。所有方法均實現了O(1)的均攤時間復雜度和O(n)的空間復雜度。研究對于其在密碼學（如流密碼密鑰序列）和CDMA（碼分多址）系統中的潛在應用具有重要意義。
亮點
令π = a1a2...an為一個n元集合{1,2,...,n}上的n階排列。排列π的縮略排列（shorthand permutation）由a1a2...an-1給出，其中缺失符號（the missing symbol）an可以輕松確定。用SP(n)表示所有n!個來自n元集合{1,2,...,n}的縮略排列的集合。一個排列的縮略通用環（shorthand universal cycle for permutations）是SP(n)的一個通用環，它是一個長度為n!的周期序列，其中SP(n)的每個元素在每個周期內恰好出現一次。例如，SP(4) = {123, 231, 312, 124, 241, 412, 132, 321, 213, 134, 341, 413, ...}。
兩種構造排列縮略通用環的高效方法
在本節中，我們將給出兩種構造排列縮略通用環的高效方法。為了更簡單地描述這些方法，我們首先在下面的引理中給出一個后續規則，該規則將[SP(n)]中的一些循環連接成一個更大的循環。以下結果稍微修改了Gabric等人研究的一個縮略排列后續規則，我們提供了一個更簡單的證明。
引理 3.1
令α = a1a2...an-1∈ SP(n) 并令an為缺失符號。那么后續規則
ρ0(α) = ( an, 如果 |a1- an| = 1;
a(這里原文公式顯示不完整，根據上下文應為返回a1或其他符號，但文檔內公式顯示異常))
一種構造排列縮略通用環的高效新方法
在本節中，我們將給出另一種構造排列縮略通用環的高效方法，該方法無需對循環進行排序，并能一步完成所有循環的連接過程。
以下定理給出了一個后續規則，用于將[SP(n)]中的所有循環連接成一個排列的縮略通用環。
定理 4.1
令α = a1a2...an-1∈ SP(n) 并且an為缺失符號，令t = min{a1, an}。那么后續規則
ρ3(α) = ( an, 如果 t = 1;
an, 如果 1 < t < n-1, |a1- an| ≠ 1 并且 a2a3...at= (t-1)(t-2)...1;
a1, )
結論
本文提供了三種簡單高效的后續規則來生成排列的縮略通用環，并且這第三種后續規則可以轉化為∏t=2n-2t!種不同的后續規則。每種后續規則都可以在O(1)的均攤時間內使用O(n)的空間，生成排列的縮略通用環的每個符號。
