我如何获得最短的随机序列，以便它编码从一个元素到另一个元素的所有可能转换？
How do I obtain the shortest random sequence such that it encodes all possible transitions from one element to another?
我正在设计一个实验，系统会提示参与者执行一系列随机操作，我将在整个实验过程中记录数据。我的意图是使用尽可能短的序列捕捉从一个动作到另一个动作的每一个可能的转换。假设有 N 种可能的操作，我正在寻找一种可以生成一组具有以下属性的随机序列的算法：
- 滑过每个序列，连续的两个元素表示从一个动作到另一个动作的转换。因此，除了序列的开始和结束之外，每个元素都将作为一个转换的结束，同时也是下一个转换的开始。从我使用小例子观察到的情况来看，这种方法似乎产生了最短的序列，同时覆盖了所有转换。
- 实现该算法的代码必须return所有此类有效的最短序列。
- 不能有两个相同的连续元素（即不允许自转换）。
- 必须使用 Python 和 MATLAB 中可用的基本函数，所以我不能使用可能在 Python 中可用但在 MATLAB 中不可用的 modules/libraries（反之亦然）。
举个例子，假设我有 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 的悬空转换，因此必须排在最后。
可能有某种替代解决方案可以利用这个特定问题的结构来产生更有效的解决方案，但如果有的话，我没有看到它。这个问题基本上是寻找最短 superpermutation 的一个规模稍小的版本，但目前还不知道有更有效的解决方案。
对于将来看到此内容的任何人：我遇到了 De Bruijn sequence 这几乎正是我想要解决我的问题的方法。文章中引用的 Python 代码非常适合我的问题。我需要做的唯一修改是在输出字符串中，我需要确保所有涉及自转换的排列（例如 AA、BB、CC 等）都折叠成单个符号（即 A、B、C 等）。
此外，正如维基百科页面所述：
... Note that these sequences are understood to "wrap around" in a cycle ...
所以这证实了我的观察，即序列总是在同一点结束和开始。可以通过向输入提供置换字符串（即输入 ABC、ACB、BAC 等）来获得多个序列，然后我们得到我们感兴趣的输出。产生的输出Python 代码似乎总是有序的。
我正在设计一个实验，系统会提示参与者执行一系列随机操作，我将在整个实验过程中记录数据。我的意图是使用尽可能短的序列捕捉从一个动作到另一个动作的每一个可能的转换。假设有 N 种可能的操作，我正在寻找一种可以生成一组具有以下属性的随机序列的算法：
- 滑过每个序列，连续的两个元素表示从一个动作到另一个动作的转换。因此，除了序列的开始和结束之外，每个元素都将作为一个转换的结束，同时也是下一个转换的开始。从我使用小例子观察到的情况来看，这种方法似乎产生了最短的序列，同时覆盖了所有转换。
- 实现该算法的代码必须return所有此类有效的最短序列。
- 不能有两个相同的连续元素（即不允许自转换）。
- 必须使用 Python 和 MATLAB 中可用的基本函数，所以我不能使用可能在 Python 中可用但在 MATLAB 中不可用的 modules/libraries（反之亦然）。
举个例子，假设我有 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 的悬空转换，因此必须排在最后。
可能有某种替代解决方案可以利用这个特定问题的结构来产生更有效的解决方案，但如果有的话，我没有看到它。这个问题基本上是寻找最短 superpermutation 的一个规模稍小的版本，但目前还不知道有更有效的解决方案。
对于将来看到此内容的任何人：我遇到了 De Bruijn sequence 这几乎正是我想要解决我的问题的方法。文章中引用的 Python 代码非常适合我的问题。我需要做的唯一修改是在输出字符串中，我需要确保所有涉及自转换的排列（例如 AA、BB、CC 等）都折叠成单个符号（即 A、B、C 等）。
此外，正如维基百科页面所述：
... Note that these sequences are understood to "wrap around" in a cycle ...
所以这证实了我的观察，即序列总是在同一点结束和开始。可以通过向输入提供置换字符串（即输入 ABC、ACB、BAC 等）来获得多个序列，然后我们得到我们感兴趣的输出。产生的输出Python 代码似乎总是有序的。