如何生成覆盖所有N种动作非自转移的最短随机序列及通用算法

你所寻找的短序列本质是无自环有向完全图的欧拉回路，可完全对齐所有提出的约束：

• 映射规则对齐：
  • 将每个动作作为图的顶点，共N个顶点
  • 将所有禁止自转移的动作组合（即i→j，i≠j的所有有序对）作为图的有向边，总边数为N*(N-1)
  • 该图的结构完全满足欧拉回路存在的充要条件：全图连通，每个顶点的入度=出度=N-1，不存在孤立节点
• 对提出的两个规律猜想的验证：
  1. 最短序列长度公式完全成立：欧拉回路遍历完所有边时，每一条边对应滑动窗口截取的一个动作转移，遍历k条边对应的线性序列长度为k+1，覆盖全部转移的最短长度就是总边数+1，即N*(N-1)+1，不存在更短的可能——任何长度小于该值的序列，最多只能包含比总边数少的转移，必然存在未覆盖的动作组合。
  2. 首尾元素相同的规律完全通用：欧拉回路的定义就是从起点出发，经过所有边后最终回到起点的闭合路径，因此拆分为线性序列时，首尾元素必然和初始起点一致。观察到“更接近循环列表”的感知是准确的：如果把序列首尾连接成环，就得到没有固定起点终点的环形转移序列，任意切割环形序列的位置得到的线性片段，都是合法的最短序列。

所有符合要求的最短序列，本质就是该图上的全部欧拉回路，使用优化版Hierholzer算法即可穷举所有解，且核心逻辑仅使用Python、MATLAB共有的基础功能，无专属模块依赖：

• 核心实现逻辑（跨语言通用）：
  1. 构建邻接表：对每个顶点，存储所有可到达的其他顶点列表（排除自指向的节点，从根源上避免连续重复元素）
  2. 从指定起点出发，通过深度优先遍历穷举所有可能的路径分支：
     • 每次从当前顶点的可用邻接列表中，依次取出每一条未走的边，标记该边为已使用（从邻接表中删除）
     • 递归沿该边走到下一个顶点，等递归分支全部返回后，将当前顶点加入路径结果
  3. 当某条路径遍历完全部N*(N-1)条边时，将路径反转后即可得到一条完整的合法最短序列；算法会遍历所有分支，最终返回全部符合要求的序列集合
• 约束匹配验证：
  • 因为邻接表不包含自环边，生成的所有序列从结构上就不会出现连续相同元素的情况
  • 算法遍历了所有可能的边选择分支，不会遗漏任何合法的最短序列
  • 仅用到列表操作、集合判断、递归/栈存储这类两个语言都内置的基础能力，不需要加载任何第三方或语言专属库

• 小规模场景验证：以提到的N=3的场景为例，按上述逻辑生成的序列，长度恒为7，无连续重复元素，恰好覆盖全部6种动作转移，和手动推导的ABCBACA、ACABCBA样例完全匹配
• 大规模场景的数量级：随着N增大，合法最短序列的数量会指数级增长，例如N=4时合法序列数已过百，N=5时会达到数十万级，实际实验中不需要枚举全部序列，只需从生成的集合中随机抽取若干平衡版本分配给不同被试，即可抵消序列顺序带来的实验偏差
• 循环序列的复用性：因为最短序列本质是闭合回路，可以把生成的环形序列作为母体，每次实验从不同的位置拆分出一段长度匹配要求的线性序列，不需要反复重新生成，进一步提高实验流程的效率

实现注意：Hierholzer算法的核心是避免重复遍历已使用的边，实现时不需要额外的复杂数据结构，仅用列表记录已走的边即可满足跨语言运行的要求。

内容的提问来源于stack exchange，提问作者STPR