我正在设计一个实验，参与者将被提示一系列随机的动作，我将在整个实验中记录数据。我的意图是用尽可能短的序列捕捉从一个动作到另一个动作的每一个可能的转变。假设有N可能的动作，我正在寻找一种算法，它可以生成一组具有以下属性的随机序列：
- 在每个序列中滑动，连续的两个元素表示从一个动作到另一个动作的转换。因此，除了序列的开始和结束之外，每个元素都将作为一个过渡的结束，也是下一个转换的开始。从我使用小例子观察到的情况来看，这种方法似乎产生了最短的序列，同时覆盖了所有的转换
- 实现算法的代码必须返回所有这样的有效最短序列
- 两个连续元素不能相同(即不允许自转换)
- 必须使用Python和MATLAB中可用的基本函数，所以我不能使用Python中可用但MATLAB中不可用的模块/库(反之亦然)
例如，假设我有3个操作：{A, B, C}。该算法应该产生的预期序列之一是：ABCBACA。在这个序列中滑动，一次取2个元素，得到{AB, BC, CB, BA, AC, CA}。正如预期的那样，这涵盖了使用长度为7的序列可能的所有6个转换。序列中没有两个相同的连续元素。该算法可能产生的另一个有效序列是：ACABCBA。在这个序列中滑动，一次取2个元素，得到{AC, CA, AB, BC, CB, BA}，因此覆盖了所有的转换，没有两个连续的元素是相同的。
我用笔和纸计算了这两个例子，但我很难看到模式，尤其是N >3。从这里开始我该怎么做？
在我的情况下，长度为N*(N-1) + 1的序列似乎是最短的序列，我认为这是有道理的。我还观察到这样的序列的开始和结束是相同的(即，如果我们从A开始，我们在A结束)。它看起来几乎是一个循环列表，而不是线性列表。这通常是真的吗？
如果我能正确理解你的要求，那么基本上你需要做的是：
- 创建一个有向图，其中每个可能的转换都有一个节点(因此一个用于AB，一个用于AC等)，并将从每个节点到以"；结束"；(所以对于AB，你可以将其连接到BA和BC——记住，它们是单向的)
- 求上图的任意哈密顿循环
你完了。问题是，在一般情况下，寻找哈密顿循环是一个NP完全问题。因此，简单地说，为大N找到一种有效的方法可能很有挑战性。如果你只需要它用于相当小的N，那么你可以选择任何找到哈密顿循环的算法并将其粘贴进去
见鬼，你可能只需要连接1的随机转换。尚未使用和2。从上一个过渡结束的任何地方开始(换句话说，随机遍历上面描述的图，而不返回到您已经访问过的节点)，如果在用完所有过渡之前用完了选项，请重新开始。它肯定会很快找到小N(比如<=6)的解，而且很明显，它找到任何有效解的概率都是相等的。
至于你关于解决方案是否总是循环的问题；是的，这是正确的。很明显，如果你考虑这样一个事实，即在最佳解决方案中，你会看到每一个过渡都只有一次，而且任何"；传出"；转换必须与一个"；传入"；相同动作的转换：例如，如果你从AB开始，你的池将包含N个形式为xA的转换，但只有N-1个Ax的转换，因此你最终将只剩下一个形式为xA的悬空转换，因此必须排在最后。
可能有某种替代解决方案可以利用这个特定问题的结构来产生更高效的解决方案，但如果有，我看不到。不过，这个问题基本上是一个小规模的寻找最短超项的版本，目前还不知道它有更高效的解决方案。
对于将来研究这个问题的人来说：我发现了德布鲁因序列，这几乎正是我想要的问题的解决方案。文章中引用的Python代码可以很好地解决我的问题。我需要做的唯一修改是，在输出字符串中，我需要确保所有涉及自转换的排列(例如AA、BB、CC等)都被折叠成单个符号(即A、B、C等)
此外，正如维基百科页面所说：
。。。注意，这些序列被理解为"；"环绕"；在一个循环中。。。
这证实了我的观察结果，即序列总是在同一点结束和开始。通过向输入(即输入ABC、ACB、BAC等)提供排列字符串可以获得多个序列，并且我们得到我们感兴趣的输出。Python代码产生的输出似乎总是有序的。