关于反演的问题

我已经在网站上读到反转的意思，如果i<j然后A[i]>A[j]，它有一些关于这方面的练习，我有很多问题，但我想先问一个，然后我会做如果我可以，我自己的其他练习！关于反演的问题

练习：什么样的置换数组（1,2，...，n）具有最高的反演数？这些是什么？ 谢谢

2010-06-20 user355002

根据您之前的问题，我将其标记为家庭作业。如果不是，请随时将其删除。如果是作业，我建议你离开它，因为如果你有任何疑问，人们会更有帮助（了解你的主题）。 – 2010-06-20 14:44:18

这不是我的家务，但我需要人们更有帮助，所以我保存这个标签:) – user355002 2010-06-20 15:20:17

显然N, ..., 2, 1具有最高的反转次数。每一对都是一个倒置。例如对于N = 6，我们有6 5 4 3 2 1。反演是6-5, 6-4, 6-3, 6-2, 6-1, 5-4, 5-3等等。他们的电话号码是N * (N - 1)/2。

2010-06-20 14:46:11

啊哈我也得到它也谢谢你的链接mathworld.wolfram.com/PermutationInversion.html – user355002 2010-06-20 15:26:17

也是这是正确的，如果数组更多，以便其倒置将更多？ – user355002 2010-06-20 15:31:07

更多按顺序不是一个定义的术语。但是直观地说，一个倒过来的排列可能会比非排列倒置的排列更多。但是，这又取决于你比较的排列。 – 2010-06-20 15:39:57

那么，身份置换（1,2，...，n）没有倒置。由于反演是一对与它们的指数相反顺序的元素，所以答案可能涉及到该置换的一些逆转。

2010-06-20 14:45:26 Amnon

有我的微妙暗示... – Amnon 2010-06-20 14:54:34

我从来没有听说过使用这种方式的术语反转。

对于N> 0，减小的长度为N的阵列具有1/2 * N *（N-1）个对与A [i] > A [j]。这是最大可能的。

2010-06-20 14:46:11

http://mathworld.wolfram.com/PermutationInversion.html – 2010-06-20 14:46:51

@Petar：谢谢。我认为Knuth不使用这个术语。 – 2010-06-21 19:05:14

回答