關於反演的問題

我已經在網站上讀到反轉的意思，如果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

回答