question about inversion

views:

answers:

question about inversion

Hi I have read something in the site that inversion means if i<j then A[i]>A[j] and it has some exercises about this , I have a lot of questions but I want to ask just one of them at first and then i will do the other exercises by myself if I can!!

Exercise: What permutation array (1,2, ..., n) has the highest number of inversion? What are these? thanks

+1 A:

Well, the identity permutation (1,2,...,n) has no inversions. Since an inversion is a pair of elements that are in reverse order than their indices, the answer probably involves some reversal of that permutation.

Amnon 2010-06-20 14:45:26

There goes my subtle hinting...

Amnon 2010-06-20 14:54:34

I have never heard the term inversion used in this way.

A decreasing array of length N, for N>0, has 1/2*N*(N-1) pairs i<j with A[i]>A[j]. This is the maximum possible.

Charles Stewart 2010-06-20 14:46:11

http://mathworld.wolfram.com/PermutationInversion.html

Petar Minchev 2010-06-20 14:46:51

@Petar: Thanks. I think Knuth doesn't use the term.

Charles Stewart 2010-06-21 19:05:14

+1 A:

Clearly N, ..., 2, 1 has the highest number of inversions. Every pair is an inversion. For example for N = 6, we have 6 5 4 3 2 1. The inversions are 6-5, 6-4, 6-3, 6-2, 6-1, 5-4, 5-3 and so on. Their number is N * (N - 1) / 2.

Petar Minchev 2010-06-20 14:46:11

aha I get it also thanks for your link mathworld.wolfram.com/PermutationInversion.html

2010-06-20 15:26:17

also is this correct that if the array is more in order its inversion will be more???

2010-06-20 15:31:07

More in order is not a defined term. But intuitively a permutation which is more reversed will probably have more inversions than a non-reversed. But again it depends on the permutations you compare.

Petar Minchev 2010-06-20 15:39:57

aha !!thanks :)

2010-06-20 15:56:06

ansaurus

tags:

views:

answers:

question about inversion

related questions