从随机有序子集重建超集
Reconstruct superset from random ordered subsets
如果我们有保留超集顺序的随机样本（例如，a出现在 b) 之前，但不一定由超集中的连续元素构成（样本可以包含空洞，例如 {a, c, d}）？此外，样本大小可以是大于或等于 2 的任意长度（1 的样本长度不能保持顺序），但我们假设在单次计算期间样本长度保持不变（无可变长度数据）。
例如，一个简单的案例是 {a, b, c}, {c, d, e} 和 {e, f, g}，一个更难的案例是 {a, f, g} , {b, e, f}, {c, d, e} 等...
这种算法有什么限制，例如。给定超集的大小和样本长度，所需的最小样本数？何时无法重建数据？等等
您可以迭代子集并使用每个子集中包含的信息来构建有向图。如果该图包含超集的所有元素，并且该图只有一条路径通过所有元素，则该路径就是超集的顺序。
实际上，将有序子集{a,b,c}中的信息添加到有向图中时，需要遵循以下三个规则：
- 添加边 a→b 和 b→c，但不添加边 a→c。
- 如果已经有一条从a到b的路径，例如a→x→y→b，则不加边a→b。
- 如果存在边 x→y，添加边 a→b 会创建一条从 x 到 y 的附加路径，例如x→a→b→z→y，然后去掉边x→y。
示例：
假设对于超集 {a,b,c,d,e,f,g,h,i,j,k,l} 我们已经将来自多个子集的信息添加到图中，并得出这种情况：
下一个子集是{b,g,h,k}。已经有一条从 b 到 g，从 h 到 k 的路径，所以我们不添加边 b→g 或 h→k。我们添加的边是 g→h:
我们现在已经创建了一条从e到h的附加路径，e→g→h，所以我们删除边e→h。我们还创建了一条从f到h的附加路径，f→g→h，所以我们去掉边f→h，得到：
从子集 {b,g,h,k} 添加信息简化了图，我们现在知道元素 g 是有序超集中的第七个元素，因为从起始元素 a 和 b 到结束的所有路径元素 k 和 l 通过它，六个元素在它之前。
(注意所有路径都经过的元素：c,g,j，将图分为四个子图：abc,cdefg,ghij,jkl，然后可以单独考虑，例如在向该子图添加新边后寻找要删除的边时。）
要知道超集的顺序，我们需要来自其他子集的信息来将图形简化到所有元素只有一条路径的点：
具有 N 个元素的超集有 2N 个唯一的有序子集；如果你知道所有这些子集，你就可以确定你知道超集的顺序。如果删除包含两个相邻元素 x 和 y 的所有子集，则这两个元素的顺序将不再为人所知。所以在最坏的情况下，你需要 2N - 2N-2 + 1 个子集才能知道超集的顺序。
在最好的情况下，你只需要一个子集，等于超集，就可以知道超集的顺序。 （而且，正如您在问题中提到的，一个子集的最后一个元素是下一个子集的第一个元素的子集链是这种最佳情况的扩展。）
如果我们有保留超集顺序的随机样本（例如，a出现在 b) 之前，但不一定由超集中的连续元素构成（样本可以包含空洞，例如 {a, c, d}）？此外，样本大小可以是大于或等于 2 的任意长度（1 的样本长度不能保持顺序），但我们假设在单次计算期间样本长度保持不变（无可变长度数据）。
例如，一个简单的案例是 {a, b, c}, {c, d, e} 和 {e, f, g}，一个更难的案例是 {a, f, g} , {b, e, f}, {c, d, e} 等...
这种算法有什么限制，例如。给定超集的大小和样本长度，所需的最小样本数？何时无法重建数据？等等
您可以迭代子集并使用每个子集中包含的信息来构建有向图。如果该图包含超集的所有元素，并且该图只有一条路径通过所有元素，则该路径就是超集的顺序。
实际上，将有序子集{a,b,c}中的信息添加到有向图中时，需要遵循以下三个规则：
- 添加边 a→b 和 b→c，但不添加边 a→c。
- 如果已经有一条从a到b的路径，例如a→x→y→b，则不加边a→b。
- 如果存在边 x→y，添加边 a→b 会创建一条从 x 到 y 的附加路径，例如x→a→b→z→y，然后去掉边x→y。
示例：
假设对于超集 {a,b,c,d,e,f,g,h,i,j,k,l} 我们已经将来自多个子集的信息添加到图中，并得出这种情况：
下一个子集是{b,g,h,k}。已经有一条从 b 到 g，从 h 到 k 的路径，所以我们不添加边 b→g 或 h→k。我们添加的边是 g→h:
我们现在已经创建了一条从e到h的附加路径，e→g→h，所以我们删除边e→h。我们还创建了一条从f到h的附加路径，f→g→h，所以我们去掉边f→h，得到：
从子集 {b,g,h,k} 添加信息简化了图，我们现在知道元素 g 是有序超集中的第七个元素，因为从起始元素 a 和 b 到结束的所有路径元素 k 和 l 通过它，六个元素在它之前。
(注意所有路径都经过的元素：c,g,j，将图分为四个子图：abc,cdefg,ghij,jkl，然后可以单独考虑，例如在向该子图添加新边后寻找要删除的边时。）
要知道超集的顺序，我们需要来自其他子集的信息来将图形简化到所有元素只有一条路径的点：
具有 N 个元素的超集有 2N 个唯一的有序子集；如果你知道所有这些子集，你就可以确定你知道超集的顺序。如果删除包含两个相邻元素 x 和 y 的所有子集，则这两个元素的顺序将不再为人所知。所以在最坏的情况下，你需要 2N - 2N-2 + 1 个子集才能知道超集的顺序。
在最好的情况下，你只需要一个子集，等于超集，就可以知道超集的顺序。 （而且，正如您在问题中提到的，一个子集的最后一个元素是下一个子集的第一个元素的子集链是这种最佳情况的扩展。）