所以我遇到了这样的问题 - 我有一些 k 元组，每个元组由 1 到 10 的一些整数组成，均匀分布到两个“子数组”（所以 1 2 3 4 5 <=> 6 7 8 9 10，对于例子）。我想要做的是在第一行中查找是否存在这样的一对（2元素组合，排列无关紧要）它总是一起出现（在同一侧，是否相邻无关紧要）在后面的行中（例如，在上面的示例中，如果我们还有 3 4 2 8 1 <=> 5 6 7 9 10 作为第二个输入行，则条件为真，因为 (1,2) 总是一起出现，所以也是(3,4) 依此类推 - 但是，这样的一对就足够了。此外，第二行打破了 (4,5) 婚姻，因为 5 在 4 的另一侧。
创建初始组合数组不应该太费时间，但是有没有更快的方法来检查是否有任何“对”被破坏（在一侧没有找到）而不是构建一个“跨数组”2元素组合表每个传入的行，然后将其中的每个元素与已经构建的初始对进行比较？这听起来真的很慢，至少可以说 n^2。有人有什么想法吗？我想不出任何其他方式。
编辑和修复：好的，我很抱歉，因为我的非正式描述似乎是，轻描淡写，令人困惑:) 这里有一些更正式的东西，然后 - 我希望现在问题的问题很清楚：
我们有 l 行 k 个整数，每行作为输入。每行由 {1, 2, ..., k} 序列的一些排列组成。我们将每行中的前 k/2 个整数视为“左侧”，将其他整数视为“右侧”。是否有任何整数 x, y 使得对于任何选定的线，它们总是位于同一侧（左侧或右侧），但不必从上到下位于同一侧（即 1 2 - 3 4, 3 4 - 1 2 完成了婚姻，因为 1 2 和 3 4 总是在一起 - 一次在左边，一次在右边）。
第 2 次编辑在我的头脑更加清醒之后，蛮力比较组合的想法似乎完全没有意义。假设我们有 k=100,000 - 那么，我们只需要在第一行输入之后管理近 25 亿个元素 - 然后，想象为第二行构建一个类似数量级的数组，并进行所有与交叉的比较-在第二行之后绝对没有结婚的那些。这需要非常长的时间，不是吗？
我想过以某种方式对双方的列求和，但这使得算法依赖于侧（即 1 2 - 3 4 与 4 3 - 2 1 不同，但事实并非如此）......事实上，我所有的想法都结束了向上依赖。可以用它做什么？