问题标签 [inversion]

P = [a1, a2, ... , aN]第一个自然数的排列N可以用一个倒数 I = [i1, i2, ... , iN]列表来表示，其中iK告诉我们有多少数大于在排列K中之前可以找到的数。KP

示例： if P = [3, 1, 4, 2], then I = [1, 2, 0, 0]（3 放在 1 之前，3 和 4 放在 2 之前，而 3 和 4 之前没有任何更大的数字）。

有一个明显的算法可以将排列从标准形式转换为反转形式并运行O(N^2)（我们只需遵循定义和计数）。逆变换也是如此（稍微不那么直接）。

有没有时间复杂度较低的算法？

给定两个列表，每个列表包含 N 个区间（数轴的子集），每个区间都有起点和终点的形式。一个列表中有多少对这些区间包含另一个列表中的区间？

例如：

如果列表 A 是{(1,7), (2,9)}并且列表 B 是{(3,6), (5,8)}

那么 A 的区间包含 B 中的区间的对数将是 3 对：

目标是为 O(n log n) 射击。

我目前的算法是先按 x 坐标排序并将其作为一个列表。然后按 y 坐标对列表进行排序，并计算两个列表之间的倒数。但我的问题是为什么这行得通？任何见解将不胜感激。

我目前正在可视化的方式是以下几何方式（其中线的每个交点都是 num 反转的计数）：

注意：我不确定如何检查列表列表中的反转。只是试图获得一种可以给出 O(n log n) 的方法。如果有任何其他方法很高兴听到建议。

输入：元素数组和这些元素子集的偏序，被视为约束集。

输出：满足偏序的数组（或任何有序序列）。

问题：如何有效地实现重新排序？与原始输入序列相比，引入的反转（或交换）的数量应尽可能小。请注意，可以为任意数量的元素定义偏序（某些元素可能不是其中的一部分）。

上下文：它源于 2 层图交叉减少的情况：在交叉减少阶段之后，我想重新排序一些节点（因此，部分顺序可能只包含一个小子集）。

总的来说，我的想法是稍微弱化这一点，并仅针对属于偏序的元素解决问题（尽管我认为这可能会导致非最佳结果）。因此，如果我有一个序列 ABCDE 并且偏序只包含 A、B 和 E，那么 C 和 D 将保持在同一个位置。它以某种方式让我想起了 Kemeny 分数，但我还不能把它变成算法。

可以肯定的是：我不是在寻找拓扑排序。这可能会引入比所需更多的反转。

编辑1：

• 更改了措辞（序列到数组）。
• 用于解决问题的额外空间量可以是任意的（嗯，多项式有界）。当然，越少越好 :) 所以，像 O(ArrayLen*ArrayLen) 这样的东西最多会很棒。
• 为什么交换或反转的最小数量：由于此过程是交叉减少的一部分，因此输入数组的排序（希望）接近最佳值，就与第二节点层的边缘交叉而言。然后，每一次额外的交换或反转可能会再次引入边缘交叉。但是在计算输出的过程中，完成的交换或移动的数量并不重要（尽管再次，线性或二次的东西会很酷），因为只有输出质量很重要。现在，我要求约束是一个总顺序，并且只检查该顺序的节点，因此解决它变得微不足道。但是偏序约束会更加灵活。

我正在寻找一种基于子集反转的排序算法。这就像煎饼排序，只是不是把所有的煎饼都放在抹刀上，你可以倒置任何你想要的子集。子集的长度无关紧要。像这样： http ://www.yourgenome.org/sites/default/files/illustrations/diagram/dna_mutations_inversion_yourgenome.png 所以我们不能简单地交换数字而不反转两者之间的一切。

我们这样做是为了确定果蝇的一个亚种如何变异成另一种。两者具有相同的基因，但顺序不同。第二个亚种的基因组是“排序的”，即基因编号为1-25。第一个亚种基因组是未分类的。因此，我们正在寻找一种排序算法。

这是我们正在研究的“基因组”（尽管我们应该能够对所有数字列表进行这项工作）：

我们正在研究两个不同的问题：

1) 对 25 个倒数最少的数字列表进行排序

2) 对移动数字最少的 25 个数字的列表进行排序 我们还想为两者建立上限和下限。

我们已经找到了一种这样的排序方法，只需从左到右，搜索下一个最低值并将其间的所有内容反转，但我们绝对确定我们应该能够更快地做到这一点。但是，我们仍然没有找到任何其他方法，所以我请求您的帮助！

现在，我们正在使用 Python 工作，因为我们在这方面拥有丰富的经验，但我对任何关于如何更有效地解决这个问题的伪代码想法都很满意。如果您认为另一种语言可能更适合，请告诉我。欢迎使用伪代码、想法、想法和实际代码！

提前致谢！

我正在尝试编写代码来查找数字数组中的反转。我已经看到使用合并排序正确执行此操作的算法，但对逻辑有疑问。

为什么我们必须计算左右子数组中的反转以及两者之间的反转？我的意思很明显这是正确的，但为什么我们不能只计算合并步骤中的所有反转呢？事实证明，在进行合并的每一级都可以直接计算反转的次数，并且在生成两倍大小的子数组后，它的任何两个元素的相对顺序在后续合并步骤中永远不会改变，这意味着我们永远不会计算任何最终不会是反转的反转。那么，逻辑有什么问题，因为它没有给出正确的答案。

如果你愿意，我可以用例子和/或代码解释更多；故意没有包含代码，所以没有人怀疑这是家庭作业。

编辑：到目前为止，我没有发现逻辑有任何问题，而是代码中的一个错误导致了错误的答案。

因此，这是在数组中查找反转的方法：

该mergeAndCount()方法的工作方式显而易见：

我调用计数设置为零的方法：findInversions(0, numbers.length - 1, 0)。

显然，问题在于count它不能在不同的递归中保持其价值。这是 Java，所以我不需要用 & 号传递它，我什至在mergeAndCount(). 那么这里有什么问题呢？

这就是问题所在：我想计算 3x3 矩阵的逆矩阵。我尝试使用solve(J)，但它给出了一条错误消息：

solve.default(J) 中的错误：“a”必须是数字矩阵。

这是矩阵J和代码：

有什么问题？？？非常感谢你们。Obs：我不能用 50 代替 T2、T3 和 T4，因为我需要重新计算多次更改 T2、T3 和 T4 值。

我试图找出任何数组中的反转数。我已经应用了归并排序。在合并子数组时，如果右子数组的任何值小于左子数组的任何值，我都会计算数量。如果数组包含大量数据，则此代码不起作用。

这是我在这个网站上的第一个问题。我（拼命地）试图在我的程序中反转一个大矩阵。我想使用 lapack 来做到这一点，我发现这个线程看起来很有希望，但我认为它是用 C++ 语言编写的。你能帮帮我吗？

在 C 中使用 lapack 计算矩阵的逆

谢谢你。

更新：你是对的，答案有点不清楚。将我发布的程序合并到我的程序后，我收到以下错误：

我想问题是我没有正确安装 llapack 库，或者我在编译时包含它。

这就是我安装库的方式（从终端，我有 Ubuntu）：

这就是我的编译方式：

我究竟做错了什么？

我正在尝试使用 MergeSort 从文件中计算反转，我的代码似乎适用于较小的文件，但较大的文件会产生错误的输出。我的代码：

反转计数.py：

应用程序.py：

答案是：2407905288，但我得到的最终打印计数是：22945388587258。我非常感谢任何帮助，因为我正在尝试自己学习算法。另外，我的问题发生在大文件上，那么我将如何调试似乎只有在输入非常大时才会出现的问题（我尝试用较小的输入对此进行测试，它给出了正确的答案）？谢谢！

I am working through a proof in which there is a hypothesis

If I use inversion H, then I recover

which is fine, but then I need to use inversion twice more to recover b and v. Is there a single command to recover a, b, v all at once?