목록에서 반전 수를 간단히 계산할 수 있습니다.

전도

유형의 요소 시퀀스에서 반전 T은의 세트에서 일부 순서 <에 따라 순서가 다르게 나타나는 한 쌍의 시퀀스 요소입니다 T.

에서 위키 백과 :

공식적으로 A(1), A(2), ..., A(n)일련의 n숫자를 보자 .
만약i < j 와 A(i) > A(j), 그 쌍은 (i,j)이라고 반전 의를 A.

그만큼 시퀀스 반전 번호 는 정렬의 일반적인 측정 방법 중 하나입니다.
공식적으로, 반전 번호는 반전 횟수, 즉,

이러한 정의를보다 명확하게하려면 sequence 예제를 고려하십시오 9, 5, 7, 6. 이 순서는 반전 (0,1), (0,2), (0,3), (2,3) 과 반전 번호가 4 있습니다.

0와 사이의 값을 원하면 1반전 숫자를로 나눌 수 있습니다 N choose 2.

목록 정렬 방식에 대해이 점수를 계산하는 알고리즘을 실제로 만들려면 다음 두 가지 방법이 있습니다.

접근법 1 (결정 론적)

자주 사용하는 정렬 알고리즘을 수정하여 실행시 수정되는 반전 수를 추적하십시오. 이것은 사소하지 않으며 선택한 정렬 알고리즘에 따라 다양한 구현이 있지만, 시작한 정렬 알고리즘보다 비싸지 않은 (복잡성 측면에서) 알고리즘으로 끝납니다.

이 경로를 사용하는 경우 “스왑”을 계산하는 것만 큼 간단하지는 않습니다. 예를 들어 Mergesort는 최악의 경우 O(N log N)이지만 내림차순으로 정렬 된 목록에서 실행하면 모든 N choose 2반전 이 수정됩니다 . 그것은 작업 O(N^2)에서 수정 된 반전 O(N log N)입니다. 따라서 일부 작업은 불가피하게 한 번에 두 개 이상의 반전을 수정해야합니다. 구현에주의를 기울여야합니다. 참고 : O(N log N)복잡 하게이 작업을 수행 할 수 있습니다 .

관련 : 순열에서 “반전”수 계산

접근법 2 (확률 론적)

• 무작위로 샘플 쌍 (i,j),i != j
• 각 쌍에 대해 list[min(i,j)] < list[max(i,j)](0 또는 1)
• 이 비교의 평균을 계산 한 다음 N choose 2

나는 당신이 정확성을 요구하지 않는 한 개인적으로 확률 론적 접근을 할 것입니다-구현하기가 쉽기 때문입니다.

당신이 정말로 원하는 것은 값 (경우 z'사이) -1에 (정렬 내림차순) 1(정렬 오름차순)는, 당신은 단순히 위의 값 (매핑 할 수 있습니다 z사이에), 0(정렬 오름차순) 및 1공식을 사용하여이 범위 (정렬 내림차순) :

z' = -2 * z + 1

답변

#! ruby
d = -> a { a.zip( a.sort ).map { |u, v| ( u - v ) ** 2 }.reduce( :+ ) ** 0.5 }

a = 8, 7, 3, 4, 10, 9, 6, 2, 5, 1
d.( a ) #=> 15.556
d.( a.sort ) #=> 0.0
d.( a.sort.reverse ) # => 18.166 is the worrst case

my_list = [1,4,5,6,9,-1,5,3,55,11,12,13,14]

right_comparison_count = 0

for i in range(len(my_list)-1):
    if my_list[i] < my_list[i+1]: # Assume you want to it ascending order
        right_comparison_count += 1

if right_comparison_count == 0:
    result = -1
else:
    result = float(right_comparison_count) / float((len(my_list) - 1))

print result