Подсчет инверсий в массиве
Я разрабатываю алгоритм, чтобы сделать следующее: данный массив A[1... n], для каждого i < jнайти все пары инверсий, такие что A[i] > A[j], Я использую сортировку слиянием и копирую массив A в массив B, а затем сравниваю два массива, но мне трудно понять, как я могу использовать это, чтобы найти число инверсий. Любые советы или помощь будет принята с благодарностью.
40 ответов
Единственный совет, который я мог бы дать этому (который выглядит подозрительно, как домашний вопрос;)) - сначала сделать это вручную с небольшим набором цифр (например, 5), а затем записать шаги, которые вы предприняли для решения проблемы.
Это должно позволить вам найти общее решение, которое вы можете использовать для написания кода.
Итак, вот решение O(n log n) в Java.
long merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, count = 0;
while (i < left.length || j < right.length) {
if (i == left.length) {
arr[i+j] = right[j];
j++;
} else if (j == right.length) {
arr[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
arr[i+j] = left[i];
i++;
} else {
arr[i+j] = right[j];
count += left.length-i;
j++;
}
}
return count;
}
long invCount(int[] arr) {
if (arr.length < 2)
return 0;
int m = (arr.length + 1) / 2;
int left[] = Arrays.copyOfRange(arr, 0, m);
int right[] = Arrays.copyOfRange(arr, m, arr.length);
return invCount(left) + invCount(right) + merge(arr, left, right);
}
Это почти нормальная сортировка слиянием, вся магия скрыта в функции слияния. Обратите внимание, что при сортировке алгоритм удаляет инверсии. При этом алгоритм слияния подсчитывает количество удаленных инверсий (отсортировано, можно сказать).
Единственный момент, когда инверсии удаляются, - это когда алгоритм берет элемент с правой стороны массива и объединяет его с основным массивом. Число инверсий, удаленных этой операцией, является количеством элементов, оставшихся от левого массива, который должен быть объединен.:)
Надеюсь, это достаточно объяснительно.
Я нашел его за O(n * log n) следующим способом.
- Объединить массив сортировки A и создать копию (массив B)
Возьмите A[1] и найдите его позицию в отсортированном массиве B с помощью бинарного поиска. Число инверсий для этого элемента будет на единицу меньше номера индекса его позиции в B, поскольку каждое нижнее число, которое появляется после первого элемента A, будет инверсией.
2а. накапливать количество инверсий, чтобы противостоять переменной num_inversions.
2b. удалить A[1] из массива A, а также из соответствующей позиции в массиве B
- перезапустите с шага 2, пока больше не будет элементов в A.
Вот пример запуска этого алгоритма. Исходный массив A = (6, 9, 1, 14, 8, 12, 3, 2)
1: объединить сортировку и скопировать в массив B
B = (1, 2, 3, 6, 8, 9, 12, 14)
2: Возьмите A[1] и двоичный поиск, чтобы найти его в массиве B
A[1] = 6
B = (1, 2, 3, 6, 8, 9, 12, 14)
6 находится в 4-й позиции массива B, таким образом, есть 3 инверсии. Мы знаем это, потому что 6 был в первой позиции в массиве A, таким образом, любой элемент с более низким значением, который впоследствии появляется в массиве A, будет иметь индекс j > i (поскольку i в этом случае равно 1).
2.b: Удалить A[1] из массива A, а также из соответствующей позиции в массиве B (полужирные элементы удалены).
A = (6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)
B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)
3: перезапустите шаг 2 для новых массивов A и B.
A[1] = 9
B = (1, 2, 3, 8, 9, 12, 14)
9 теперь находится в 5-й позиции массива B, таким образом, есть 4 инверсии. Мы знаем это, потому что 9 было в первой позиции в массиве A, таким образом любой элемент с более низким значением, который впоследствии появляется, имел бы индекс j > i (так как i в этом случае снова равно 1). Удалить A[1] из массива A, а также из соответствующей позиции в массиве B (элементы, выделенные жирным шрифтом, удалены)
A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)
B = (1, 2, 3, 8, 9, 12, 14) = (1, 2, 3, 8, 12, 14)
Продолжение в этом ключе даст нам общее количество инверсий для массива A после завершения цикла.
Шаг 1 (сортировка слиянием) потребует O(n * log n) для выполнения. Шаг 2 будет выполняться n раз, и при каждом выполнении будет выполняться двоичный поиск, для выполнения которого требуется O(log n) в общей сложности O(n * log n). Таким образом, общее время работы составит O(n * log n) + O(n * log n) = O(n * log n).
Спасибо за вашу помощь. Запись образцов массивов на листе бумаги действительно помогла визуализировать проблему.
Интересно, почему никто еще не упомянул деревья с двоичными индексами. Вы можете использовать один для поддержания сумм префиксов для значений ваших элементов перестановки. Затем вы можете просто перейти справа налево и посчитать для каждого элемента количество элементов меньше его справа:
def count_inversions(a):
res = 0
counts = [0]*(len(a)+1)
rank = { v : i+1 for i, v in enumerate(sorted(a)) }
for x in reversed(a):
i = rank[x] - 1
while i:
res += counts[i]
i -= i & -i
i = rank[x]
while i <= len(a):
counts[i] += 1
i += i & -i
return res
Сложность O(n log n), а постоянный коэффициент очень низок.
В питоне
# O(n log n)
def count_inversion(lst):
return merge_count_inversion(lst)[1]
def merge_count_inversion(lst):
if len(lst) <= 1:
return lst, 0
middle = int( len(lst) / 2 )
left, a = merge_count_inversion(lst[:middle])
right, b = merge_count_inversion(lst[middle:])
result, c = merge_count_split_inversion(left, right)
return result, (a + b + c)
def merge_count_split_inversion(left, right):
result = []
count = 0
i, j = 0, 0
left_len = len(left)
while i < left_len and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
count += left_len - i
j += 1
result += left[i:]
result += right[j:]
return result, count
#test code
input_array_1 = [] #0
input_array_2 = [1] #0
input_array_3 = [1, 5] #0
input_array_4 = [4, 1] #1
input_array_5 = [4, 1, 2, 3, 9] #3
input_array_6 = [4, 1, 3, 2, 9, 5] #5
input_array_7 = [4, 1, 3, 2, 9, 1] #8
print count_inversion(input_array_1)
print count_inversion(input_array_2)
print count_inversion(input_array_3)
print count_inversion(input_array_4)
print count_inversion(input_array_5)
print count_inversion(input_array_6)
print count_inversion(input_array_7)
Основная цель этого ответа - сравнить скорости различных версий Python, найденных здесь, но у меня также есть несколько собственных вкладов. (FWIW, я только что обнаружил этот вопрос во время поиска дубликатов).
Относительная скорость выполнения алгоритмов, реализованных в CPython, может отличаться от ожидаемой от простого анализа алгоритмов и опыта работы с другими языками. Это потому, что Python предоставляет много мощных функций и методов, реализованных в C, которые могут работать со списками и другими коллекциями со скоростью, близкой к скорости, которую можно получить на полностью скомпилированном языке, поэтому эти операции выполняются намного быстрее, чем эквивалентные алгоритмы, реализованные "вручную" с Python. код.
Код, использующий преимущества этих инструментов, часто может превзойти теоретически превосходные алгоритмы, которые пытаются делать все с помощью операций Python над отдельными элементами коллекции. Конечно, фактическое количество обрабатываемых данных также влияет на это. Но для небольших объемов данных код, использующий алгоритм O(n²), работающий на скорости C, может легко превзойти алгоритм O(n log n), который выполняет основную часть своей работы с отдельными операциями Python.
Многие из опубликованных ответов на этот вопрос подсчета инверсий используют алгоритм, основанный на сортировке слиянием. Теоретически, это хороший подход, если только размер массива не очень мал. Но встроенный в Python TimSort (гибридный алгоритм стабильной сортировки, полученный из сортировки слиянием и вставкой) работает на скорости C, и сортировка слиянием, написанная вручную в Python, не может рассчитывать на конкуренцию за скорость.
Одно из наиболее интригующих решений здесь, в ответе, опубликованном Niklas B, использует встроенную сортировку для определения ранжирования элементов массива и двоичное индексированное дерево (также называемое деревом Фенвика) для хранения кумулятивных сумм, необходимых для вычисления инверсии. сосчитать. Пытаясь понять эту структуру данных и алгоритм Никласа, я написал несколько собственных вариантов (опубликовано ниже). Но я также обнаружил, что для умеренных размеров списка на самом деле быстрее использовать встроенный в Python sum функции, чем прекрасное дерево Фенвика.
def count_inversions(a):
total = 0
counts = [0] * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += sum(counts[:i])
counts[i] += 1
return total
В конце концов, когда размер списка достигает 500, O(n²) аспект вызова sum внутри этого for Петля поднимает свою уродливую голову, и производительность начинает резко падать.
Mergesort - не единственная сортировка O (nlogn), и некоторые другие могут использоваться для подсчета инверсий. В ответе prasadvk используется сортировка двоичного дерева, однако его код, по-видимому, написан на C++ или одной из его производных. Итак, я добавил версию Python. Первоначально я использовал класс для реализации узлов дерева, но обнаружил, что dict заметно быстрее. В конце концов я использовал список, который еще быстрее, хотя он делает код немного менее читабельным.
Одним из преимуществ сортировки деревьев является то, что намного проще реализовать итеративно, чем сортировку слиянием. Python не оптимизирует рекурсию и имеет предел глубины рекурсии (хотя он может быть увеличен, если он вам действительно нужен). И, конечно, вызовы функций Python относительно медленны, поэтому, когда вы пытаетесь оптимизировать скорость, полезно избегать вызовов функций, когда это практически возможно.
Другой вид O (nlogn) - почтенный сорт radix. Большим преимуществом является то, что он не сравнивает ключи друг с другом. Недостатком является то, что он лучше всего работает на смежных последовательностях целых чисел, в идеале это перестановка целых чисел в range(b**m) где b обычно составляет 2. Я добавил несколько версий, основанных на радикальной сортировке, после попытки прочитать счетные инверсии, автономный счет ортогонального диапазона и связанные с этим проблемы, связанные с вычислением количества "инверсий" в перестановке.
Эффективно использовать основную сортировку для подсчета инверсий в общей последовательности seq длиной п мы можем создать перестановку range(n) имеет столько же инверсий, сколько seq, Мы можем сделать это за (в худшем случае) O(nlogn) время через TimSort. Хитрость заключается в том, чтобы переставить индексы seq сортировкой seq, Это проще объяснить на небольшом примере.
seq = [15, 14, 11, 12, 10, 13]
b = [t[::-1] for t in enumerate(seq)]
print(b)
b.sort()
print(b)
выход
[(15, 0), (14, 1), (11, 2), (12, 3), (10, 4), (13, 5)]
[(10, 4), (11, 2), (12, 3), (13, 5), (14, 1), (15, 0)]
Сортируя пары (значение, индекс) seq мы переставили индексы seq с таким же количеством свопов, которые требуется поставить seq в исходном порядке из отсортированного порядка. Мы можем создать эту перестановку, отсортировав range(n) с подходящей ключевой функцией:
print(sorted(range(len(seq)), key=lambda k: seq[k]))
выход
[4, 2, 3, 5, 1, 0]
Мы можем избежать этого lambda используя seq "s .__getitem__ метод:
sorted(range(len(seq)), key=seq.__getitem__)
Это только немного быстрее, но мы ищем все улучшения скорости, которые мы можем получить.;)
Код ниже выполняет timeit тесты всех существующих алгоритмов Python на этой странице, а также несколько моих собственных: пара версий с грубой силой O(n²), несколько вариантов алгоритма Niklas B и, конечно, один, основанный на сортировке слиянием (которую я написал без ссылки на существующие ответы). Он также имеет мой основанный на списке древовидный код, примерно полученный из кода prasadvk, и различные функции, основанные на радикальной сортировке, некоторые используют стратегию, подобную подходам слияния, а некоторые используют sum или дерево Фенвика.
Эта программа измеряет время выполнения каждой функции в последовательности случайных списков целых чисел; он также может проверить, что каждая функция дает те же результаты, что и другие, и что она не изменяет список ввода.
каждый timeit вызов дает вектор, содержащий 3 результата, которые я сортирую. Основное значение, которое следует здесь рассмотреть, - это минимальное значение, остальные значения просто указывают на то, насколько надежным является это минимальное значение, как обсуждалось в примечании к timeit модульная документация
К сожалению, вывод этой программы слишком велик, чтобы включить его в этот ответ, поэтому я публикую его в своем ответе (вики).
Вывод получен из 3 запусков на моей старой 32-битной одноядерной машине с частотой 2 ГГц, работающей на Python 3.6.0, в старом дистрибутиве, производном от Debian. YMMV. Во время тестов я закрыл свой веб-браузер и отключился от маршрутизатора, чтобы минимизировать влияние других задач на процессор.
При первом запуске проверяются все функции с размерами списка от 5 до 320, с размерами цикла от 4096 до 64 (поскольку размер списка удваивается, размер цикла уменьшается вдвое). Случайный пул, используемый для построения каждого списка, в два раза меньше самого списка, поэтому мы, вероятно, получим много дубликатов. Некоторые из алгоритмов подсчета инверсий более чувствительны к дубликатам, чем другие.
Во втором прогоне используются большие списки: от 640 до 10240 и фиксированный размер цикла, равный 8. Чтобы сэкономить время, он исключает некоторые из самых медленных функций из тестов. Мои функции грубой силы O(n²) слишком медленны при таких размерах, и, как упоминалось ранее, мой код, который использует sum, который хорошо работает с маленькими и средними списками, просто не может идти в ногу с большими списками.
Финальный прогон охватывает список размером от 20480 до 655360 и фиксированный размер цикла 4 с 8 самыми быстрыми функциями. Для списков размером до 40000 или около того код Тима Бабича является явным победителем. Молодец, Тим! Код Никласа Б также является хорошим универсальным исполнителем, хотя он побежден в меньших списках. Код "python", основанный на делении пополам, также работает довольно хорошо, хотя кажется, что он немного медленнее с огромными списками с большим количеством дубликатов, вероятно, из-за этой линейной while цикл, который он использует, чтобы перешагнуть обманщиков
Однако для очень больших размеров списков алгоритмы на основе деления пополам не могут конкурировать с настоящими алгоритмами O (nlogn).
#!/usr/bin/env python3
''' Test speeds of various ways of counting inversions in a list
The inversion count is a measure of how sorted an array is.
A pair of items in a are inverted if i < j but a[j] > a[i]
See https://stackru.com/questions/337664/counting-inversions-in-an-array
This program contains code by the following authors:
mkso
Niklas B
B. M.
Tim Babych
python
Zhe Hu
prasadvk
noman pouigt
PM 2Ring
Timing and verification code by PM 2Ring
Collated 2017.12.16
Updated 2017.12.21
'''
from timeit import Timer
from random import seed, randrange
from bisect import bisect, insort_left
seed('A random seed string')
# Merge sort version by mkso
def count_inversion_mkso(lst):
return merge_count_inversion(lst)[1]
def merge_count_inversion(lst):
if len(lst) <= 1:
return lst, 0
middle = len(lst) // 2
left, a = merge_count_inversion(lst[:middle])
right, b = merge_count_inversion(lst[middle:])
result, c = merge_count_split_inversion(left, right)
return result, (a + b + c)
def merge_count_split_inversion(left, right):
result = []
count = 0
i, j = 0, 0
left_len = len(left)
while i < left_len and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
count += left_len - i
j += 1
result += left[i:]
result += right[j:]
return result, count
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Using a Binary Indexed Tree, aka a Fenwick tree, by Niklas B.
def count_inversions_NiklasB(a):
res = 0
counts = [0] * (len(a) + 1)
rank = {v: i for i, v in enumerate(sorted(a), 1)}
for x in reversed(a):
i = rank[x] - 1
while i:
res += counts[i]
i -= i & -i
i = rank[x]
while i <= len(a):
counts[i] += 1
i += i & -i
return res
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by B.M
# Modified by PM 2Ring to deal with the global counter
bm_count = 0
def merge_count_BM(seq):
global bm_count
bm_count = 0
sort_bm(seq)
return bm_count
def merge_bm(l1,l2):
global bm_count
l = []
while l1 and l2:
if l1[-1] <= l2[-1]:
l.append(l2.pop())
else:
l.append(l1.pop())
bm_count += len(l2)
l.reverse()
return l1 + l2 + l
def sort_bm(l):
t = len(l) // 2
return merge_bm(sort_bm(l[:t]), sort_bm(l[t:])) if t > 0 else l
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by Tim Babych
def solution_TimBabych(A):
sorted_left = []
res = 0
for i in range(1, len(A)):
insort_left(sorted_left, A[i-1])
# i is also the length of sorted_left
res += (i - bisect(sorted_left, A[i]))
return res
# Slightly faster, except for very small lists
def solutionE_TimBabych(A):
res = 0
sorted_left = []
for i, u in enumerate(A):
# i is also the length of sorted_left
res += (i - bisect(sorted_left, u))
insort_left(sorted_left, u)
return res
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by "python"
def solution_python(A):
B = list(A)
B.sort()
inversion_count = 0
for i in range(len(A)):
j = binarySearch_python(B, A[i])
while B[j] == B[j - 1]:
if j < 1:
break
j -= 1
inversion_count += j
B.pop(j)
return inversion_count
def binarySearch_python(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
return midpoint
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by Zhe Hu
def inv_cnt_ZheHu(a):
_, count = inv_cnt(a.copy())
return count
def inv_cnt(a):
n = len(a)
if n==1:
return a, 0
left = a[0:n//2] # should be smaller
left, cnt1 = inv_cnt(left)
right = a[n//2:] # should be larger
right, cnt2 = inv_cnt(right)
cnt = 0
i_left = i_right = i_a = 0
while i_a < n:
if (i_right>=len(right)) or (i_left < len(left)
and left[i_left] <= right[i_right]):
a[i_a] = left[i_left]
i_left += 1
else:
a[i_a] = right[i_right]
i_right += 1
if i_left < len(left):
cnt += len(left) - i_left
i_a += 1
return (a, cnt1 + cnt2 + cnt)
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by noman pouigt
# From https://stackru.com/q/47830098
def reversePairs_nomanpouigt(nums):
def merge(left, right):
if not left or not right:
return (0, left + right)
#if everything in left is less than right
if left[len(left)-1] < right[0]:
return (0, left + right)
else:
left_idx, right_idx, count = 0, 0, 0
merged_output = []
# check for condition before we merge it
while left_idx < len(left) and right_idx < len(right):
#if left[left_idx] > 2 * right[right_idx]:
if left[left_idx] > right[right_idx]:
count += len(left) - left_idx
right_idx += 1
else:
left_idx += 1
#merging the sorted list
left_idx, right_idx = 0, 0
while left_idx < len(left) and right_idx < len(right):
if left[left_idx] > right[right_idx]:
merged_output += [right[right_idx]]
right_idx += 1
else:
merged_output += [left[left_idx]]
left_idx += 1
if left_idx == len(left):
merged_output += right[right_idx:]
else:
merged_output += left[left_idx:]
return (count, merged_output)
def partition(nums):
count = 0
if len(nums) == 1 or not nums:
return (0, nums)
pivot = len(nums)//2
left_count, l = partition(nums[:pivot])
right_count, r = partition(nums[pivot:])
temp_count, temp_list = merge(l, r)
return (temp_count + left_count + right_count, temp_list)
return partition(nums)[0]
# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# PM 2Ring
def merge_PM2R(seq):
seq, count = merge_sort_count_PM2R(seq)
return count
def merge_sort_count_PM2R(seq):
mid = len(seq) // 2
if mid == 0:
return seq, 0
left, left_total = merge_sort_count_PM2R(seq[:mid])
right, right_total = merge_sort_count_PM2R(seq[mid:])
total = left_total + right_total
result = []
i = j = 0
left_len, right_len = len(left), len(right)
while i < left_len and j < right_len:
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
total += left_len - i
result.extend(left[i:])
result.extend(right[j:])
return result, total
def rank_sum_PM2R(a):
total = 0
counts = [0] * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += sum(counts[:i])
counts[i] += 1
return total
# Fenwick tree functions adapted from C code on Wikipedia
def fen_sum(tree, i):
''' Return the sum of the first i elements, 0 through i-1 '''
total = 0
while i:
total += tree[i-1]
i -= i & -i
return total
def fen_add(tree, delta, i):
''' Add delta to element i and thus
to fen_sum(tree, j) for all j > i
'''
size = len(tree)
while i < size:
tree[i] += delta
i += (i+1) & -(i+1)
def fenwick_PM2R(a):
total = 0
counts = [0] * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += fen_sum(counts, i)
fen_add(counts, 1, i)
return total
def fenwick_inline_PM2R(a):
total = 0
size = len(a)
counts = [0] * size
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
j = i + 1
while i:
total += counts[i]
i -= i & -i
while j < size:
counts[j] += 1
j += j & -j
return total
def bruteforce_loops_PM2R(a):
total = 0
for i in range(1, len(a)):
u = a[i]
for j in range(i):
if a[j] > u:
total += 1
return total
def bruteforce_sum_PM2R(a):
return sum(1 for i in range(1, len(a)) for j in range(i) if a[j] > a[i])
# Using binary tree counting, derived from C++ code (?) by prasadvk
# https://stackru.com/a/16056139
def ltree_count_PM2R(a):
total, root = 0, None
for u in a:
# Store data in a list-based tree structure
# [data, count, left_child, right_child]
p = [u, 0, None, None]
if root is None:
root = p
continue
q = root
while True:
if p[0] < q[0]:
total += 1 + q[1]
child = 2
else:
q[1] += 1
child = 3
if q[child]:
q = q[child]
else:
q[child] = p
break
return total
# Counting based on radix sort, recursive version
def radix_partition_rec(a, L):
if len(a) < 2:
return 0
if len(a) == 2:
return a[1] < a[0]
left, right = [], []
count = 0
for u in a:
if u & L:
right.append(u)
else:
count += len(right)
left.append(u)
L >>= 1
if L:
count += radix_partition_rec(left, L) + radix_partition_rec(right, L)
return count
# The following functions determine swaps using a permutation of
# range(len(a)) that has the same inversion count as `a`. We can create
# this permutation with `sorted(range(len(a)), key=lambda k: a[k])`
# but `sorted(range(len(a)), key=a.__getitem__)` is a little faster.
# Counting based on radix sort, iterative version
def radix_partition_iter(seq, L):
count = 0
parts = [seq]
while L and parts:
newparts = []
for a in parts:
if len(a) < 2:
continue
if len(a) == 2:
count += a[1] < a[0]
continue
left, right = [], []
for u in a:
if u & L:
right.append(u)
else:
count += len(right)
left.append(u)
if left:
newparts.append(left)
if right:
newparts.append(right)
parts = newparts
L >>= 1
return count
def perm_radixR_PM2R(a):
size = len(a)
b = sorted(range(size), key=a.__getitem__)
n = size.bit_length() - 1
return radix_partition_rec(b, 1 << n)
def perm_radixI_PM2R(a):
size = len(a)
b = sorted(range(size), key=a.__getitem__)
n = size.bit_length() - 1
return radix_partition_iter(b, 1 << n)
# Plain sum of the counts of the permutation
def perm_sum_PM2R(a):
total = 0
size = len(a)
counts = [0] * size
for i in reversed(sorted(range(size), key=a.__getitem__)):
total += sum(counts[:i])
counts[i] = 1
return total
# Fenwick sum of the counts of the permutation
def perm_fenwick_PM2R(a):
total = 0
size = len(a)
counts = [0] * size
for i in reversed(sorted(range(size), key=a.__getitem__)):
j = i + 1
while i:
total += counts[i]
i -= i & -i
while j < size:
counts[j] += 1
j += j & -j
return total
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# All the inversion-counting functions
funcs = (
solution_TimBabych,
solutionE_TimBabych,
solution_python,
count_inversion_mkso,
count_inversions_NiklasB,
merge_count_BM,
inv_cnt_ZheHu,
reversePairs_nomanpouigt,
fenwick_PM2R,
fenwick_inline_PM2R,
merge_PM2R,
rank_sum_PM2R,
bruteforce_loops_PM2R,
bruteforce_sum_PM2R,
ltree_count_PM2R,
perm_radixR_PM2R,
perm_radixI_PM2R,
perm_sum_PM2R,
perm_fenwick_PM2R,
)
def time_test(seq, loops, verify=False):
orig = seq
timings = []
for func in funcs:
seq = orig.copy()
value = func(seq) if verify else None
t = Timer(lambda: func(seq))
result = sorted(t.repeat(3, loops))
timings.append((result, func.__name__, value))
assert seq==orig, 'Sequence altered by {}!'.format(func.__name__)
first = timings[0][-1]
timings.sort()
for result, name, value in timings:
result = ', '.join([format(u, '.5f') for u in result])
print('{:24} : {}'.format(name, result))
if verify:
# Check that all results are identical
bad = ['%s: %d' % (name, value)
for _, name, value in timings if value != first]
if bad:
print('ERROR. Value: {}, bad: {}'.format(first, ', '.join(bad)))
else:
print('Value: {}'.format(first))
print()
#Run the tests
size, loops = 5, 1 << 12
verify = True
for _ in range(7):
hi = size // 2
print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
seq = [randrange(hi) for _ in range(size)]
time_test(seq, loops, verify)
loops >>= 1
size <<= 1
#size, loops = 640, 8
#verify = False
#for _ in range(5):
#hi = size // 2
#print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
#seq = [randrange(hi) for _ in range(size)]
#time_test(seq, loops, verify)
#size <<= 1
#size, loops = 163840, 4
#verify = False
#for _ in range(3):
#hi = size // 2
#print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
#seq = [randrange(hi) for _ in range(size)]
#time_test(seq, loops, verify)
#size <<= 1
У меня был вопрос, похожий на этот вопрос, на самом деле. Я был ограничен тем, что он должен иметь эффективность O(nlogn).
Я использовал предложенную вами идею использования Mergesort, поскольку она уже имеет правильную эффективность. Я просто вставил некоторый код в функцию слияния, которая была в основном: всякий раз, когда число из массива справа добавляется в выходной массив, я добавляю к общему количеству инверсий количество чисел, оставшихся в левом массиве.
Это имеет большой смысл для меня сейчас, когда я достаточно об этом подумал. Вы подсчитываете, сколько раз перед любыми числами стоит большее число.
НТН.
Количество инверсий можно узнать, проанализировав процесс слияния в сортировке слиянием: 
При копировании элемента из второго массива в массив слияния (9 в данном примере) он сохраняет свое место относительно других элементов. При копировании элемента из первого массива в массив слияния (здесь 5) он инвертируется со всеми элементами, остающимися во втором массиве (2 инверсии с 3 и 4). Поэтому небольшая модификация сортировки слиянием может решить проблему в O(n ln n).
Например, просто раскомментируйте две строки # в коде Python слияния, чтобы получить счетчик.
def merge(l1,l2):
l = []
# global count
while l1 and l2:
if l1[-1] <= l2[-1]:
l.append(l2.pop())
else:
l.append(l1.pop())
# count += len(l2)
l.reverse()
return l1 + l2 + l
def sort(l):
t = len(l) // 2
return merge(sort(l[:t]), sort(l[t:])) if t > 0 else l
count=0
print(sort([5,1,2,4,9,3]), count)
# [1, 2, 3, 4, 5, 9] 6
РЕДАКТИРОВАТЬ 1
Эту же задачу можно решить с помощью стабильной версии быстрой сортировки, которая, как известно, немного быстрее:
def part(l):
pivot=l[-1]
small,big = [],[]
count = big_count = 0
for x in l:
if x <= pivot:
small.append(x)
count += big_count
else:
big.append(x)
big_count += 1
return count,small,big
def quick_count(l):
if len(l)<2 : return 0
count,small,big = part(l)
small.pop()
return count + quick_count(small) + quick_count(big)
Выбрав pivot в качестве последнего элемента, инверсии хорошо учтены, и время выполнения на 40% лучше, чем слияние выше.
РЕДАКТИРОВАТЬ 2
Для производительности в python, версия numpy & numba:
Сначала часть numpy, в которой используется argsort O (n ln n):
def count_inversions(a):
n = a.size
counts = np.arange(n) & -np.arange(n) # The BIT
ags = a.argsort(kind='mergesort')
return BIT(ags,counts,n)
И часть Numba для эффективного подхода BIT:
@numba.njit
def BIT(ags,counts,n):
res = 0
for x in ags :
i = x
while i:
res += counts[i]
i -= i & -i
i = x+1
while i < n:
counts[i] -= 1
i += i & -i
return res
Обратите внимание, что ответ Джеффри Ирвинга неверен.
Количество инверсий в массиве составляет половину общего расстояния, которое элементы должны быть перемещены для сортировки массива. Следовательно, его можно вычислить, отсортировав массив, сохранив полученную перестановку p[i], а затем вычислив сумму abs(p[i]-i)/2. Это занимает O(n log n) времени, что является оптимальным.
Альтернативный метод приведен на http://mathworld.wolfram.com/PermutationInversion.html. Этот метод эквивалентен сумме max(0, p[i]-i), которая равна сумме abs(p[i]-i])/2, так как общее расстояние, на которое элементы перемещаются влево, равно элементы общего расстояния перемещаются вправо.
Возьмем последовательность { 3, 2, 1 } в качестве примера. Существует три инверсии: (3, 2), (3, 1), (2, 1), поэтому число инверсий равно 3. Однако, согласно указанному методу, ответ был бы 2.
Проверьте это: http://www.cs.jhu.edu/~xfliu/600.363_F03/hw_solution/solution1.pdf
Я надеюсь, что это даст вам правильный ответ.
- 2-3 часть инверсии (d)
- Это время выполнения O(nlogn)
Вот одно из возможных решений с вариацией двоичного дерева. Он добавляет поле с именем rightSubTreeSize для каждого узла дерева. Продолжайте вставлять числа в двоичное дерево в порядке их появления в массиве. Если число идет lhs узла, счетчик инверсии для этого элемента будет (1 + rightSubTreeSize). Поскольку все эти элементы больше, чем текущий элемент, и они появились бы раньше в массиве. Если элемент переходит к правой части узла, просто увеличьте его rightSubTreeSize. Ниже приведен код.
Node {
int data;
Node* left, *right;
int rightSubTreeSize;
Node(int data) {
rightSubTreeSize = 0;
}
};
Node* root = null;
int totCnt = 0;
for(i = 0; i < n; ++i) {
Node* p = new Node(a[i]);
if(root == null) {
root = p;
continue;
}
Node* q = root;
int curCnt = 0;
while(q) {
if(p->data <= q->data) {
curCnt += 1 + q->rightSubTreeSize;
if(q->left) {
q = q->left;
} else {
q->left = p;
break;
}
} else {
q->rightSubTreeSize++;
if(q->right) {
q = q->right;
} else {
q->right = p;
break;
}
}
}
totCnt += curCnt;
}
return totCnt;
Этот ответ содержит результаты timeit Тесты производятся по коду моего основного ответа. Пожалуйста, смотрите этот ответ для деталей!
count_inversions speed test results
Size = 5, hi = 2, 4096 loops
ltree_count_PM2R : 0.04871, 0.04872, 0.04876
bruteforce_loops_PM2R : 0.05696, 0.05700, 0.05776
solution_TimBabych : 0.05760, 0.05822, 0.05943
solutionE_TimBabych : 0.06642, 0.06704, 0.06760
bruteforce_sum_PM2R : 0.07523, 0.07545, 0.07563
perm_sum_PM2R : 0.09873, 0.09875, 0.09935
rank_sum_PM2R : 0.10449, 0.10463, 0.10468
solution_python : 0.13034, 0.13061, 0.13221
fenwick_inline_PM2R : 0.14323, 0.14610, 0.18802
perm_radixR_PM2R : 0.15146, 0.15203, 0.15235
merge_count_BM : 0.16179, 0.16267, 0.16467
perm_radixI_PM2R : 0.16200, 0.16202, 0.16768
perm_fenwick_PM2R : 0.16887, 0.16920, 0.17075
merge_PM2R : 0.18262, 0.18271, 0.18418
count_inversions_NiklasB : 0.19183, 0.19279, 0.20388
count_inversion_mkso : 0.20060, 0.20141, 0.20398
inv_cnt_ZheHu : 0.20815, 0.20841, 0.20906
fenwick_PM2R : 0.22109, 0.22137, 0.22379
reversePairs_nomanpouigt : 0.29620, 0.29689, 0.30293
Value: 5
Size = 10, hi = 5, 2048 loops
solution_TimBabych : 0.05954, 0.05989, 0.05991
solutionE_TimBabych : 0.05970, 0.05972, 0.05998
perm_sum_PM2R : 0.07517, 0.07519, 0.07520
ltree_count_PM2R : 0.07672, 0.07677, 0.07684
bruteforce_loops_PM2R : 0.07719, 0.07724, 0.07817
rank_sum_PM2R : 0.08587, 0.08823, 0.08864
bruteforce_sum_PM2R : 0.09470, 0.09472, 0.09484
solution_python : 0.13126, 0.13154, 0.13185
perm_radixR_PM2R : 0.14239, 0.14320, 0.14474
perm_radixI_PM2R : 0.14632, 0.14669, 0.14679
fenwick_inline_PM2R : 0.16796, 0.16831, 0.17030
perm_fenwick_PM2R : 0.18189, 0.18212, 0.18638
merge_count_BM : 0.19816, 0.19870, 0.19948
count_inversions_NiklasB : 0.21807, 0.22031, 0.22215
merge_PM2R : 0.22037, 0.22048, 0.26106
fenwick_PM2R : 0.24290, 0.24314, 0.24744
count_inversion_mkso : 0.24895, 0.24899, 0.25205
inv_cnt_ZheHu : 0.26253, 0.26259, 0.26590
reversePairs_nomanpouigt : 0.35711, 0.35762, 0.35973
Value: 20
Size = 20, hi = 10, 1024 loops
solutionE_TimBabych : 0.05687, 0.05696, 0.05720
solution_TimBabych : 0.06126, 0.06151, 0.06168
perm_sum_PM2R : 0.06875, 0.06906, 0.07054
rank_sum_PM2R : 0.07988, 0.07995, 0.08002
ltree_count_PM2R : 0.11232, 0.11239, 0.11257
bruteforce_loops_PM2R : 0.12553, 0.12584, 0.12592
solution_python : 0.13472, 0.13540, 0.13694
bruteforce_sum_PM2R : 0.15820, 0.15849, 0.16021
perm_radixI_PM2R : 0.17101, 0.17148, 0.17229
perm_radixR_PM2R : 0.17891, 0.18087, 0.18366
perm_fenwick_PM2R : 0.20554, 0.20708, 0.21412
fenwick_inline_PM2R : 0.21161, 0.21163, 0.22047
merge_count_BM : 0.24125, 0.24261, 0.24565
count_inversions_NiklasB : 0.25712, 0.25754, 0.25778
merge_PM2R : 0.26477, 0.26566, 0.31297
fenwick_PM2R : 0.28178, 0.28216, 0.29069
count_inversion_mkso : 0.30286, 0.30290, 0.30652
inv_cnt_ZheHu : 0.32024, 0.32041, 0.32447
reversePairs_nomanpouigt : 0.45812, 0.45822, 0.46172
Value: 98
Size = 40, hi = 20, 512 loops
solutionE_TimBabych : 0.05784, 0.05787, 0.05958
solution_TimBabych : 0.06452, 0.06475, 0.06479
perm_sum_PM2R : 0.07254, 0.07261, 0.07263
rank_sum_PM2R : 0.08537, 0.08540, 0.08572
ltree_count_PM2R : 0.11744, 0.11749, 0.11792
solution_python : 0.14262, 0.14285, 0.14465
perm_radixI_PM2R : 0.18774, 0.18776, 0.18922
perm_radixR_PM2R : 0.19425, 0.19435, 0.19609
bruteforce_loops_PM2R : 0.21500, 0.21511, 0.21686
perm_fenwick_PM2R : 0.23338, 0.23375, 0.23674
fenwick_inline_PM2R : 0.24947, 0.24958, 0.25189
bruteforce_sum_PM2R : 0.27627, 0.27646, 0.28041
merge_count_BM : 0.28059, 0.28128, 0.28294
count_inversions_NiklasB : 0.28557, 0.28759, 0.29022
merge_PM2R : 0.29886, 0.29928, 0.30317
fenwick_PM2R : 0.30241, 0.30259, 0.35237
count_inversion_mkso : 0.34252, 0.34356, 0.34441
inv_cnt_ZheHu : 0.37468, 0.37569, 0.37847
reversePairs_nomanpouigt : 0.50725, 0.50770, 0.50943
Value: 369
Size = 80, hi = 40, 256 loops
solutionE_TimBabych : 0.06339, 0.06373, 0.06513
solution_TimBabych : 0.06984, 0.06994, 0.07009
perm_sum_PM2R : 0.09171, 0.09172, 0.09186
rank_sum_PM2R : 0.10468, 0.10474, 0.10500
ltree_count_PM2R : 0.14416, 0.15187, 0.18541
solution_python : 0.17415, 0.17423, 0.17451
perm_radixI_PM2R : 0.20676, 0.20681, 0.20936
perm_radixR_PM2R : 0.21671, 0.21695, 0.21736
perm_fenwick_PM2R : 0.26197, 0.26252, 0.26264
fenwick_inline_PM2R : 0.28111, 0.28249, 0.28382
count_inversions_NiklasB : 0.31746, 0.32448, 0.32451
merge_count_BM : 0.31964, 0.33842, 0.35276
merge_PM2R : 0.32890, 0.32941, 0.33322
fenwick_PM2R : 0.34355, 0.34377, 0.34873
count_inversion_mkso : 0.37689, 0.37698, 0.38079
inv_cnt_ZheHu : 0.42923, 0.42941, 0.43249
bruteforce_loops_PM2R : 0.43544, 0.43601, 0.43902
bruteforce_sum_PM2R : 0.52106, 0.52160, 0.52531
reversePairs_nomanpouigt : 0.57805, 0.58156, 0.58252
Value: 1467
Size = 160, hi = 80, 128 loops
solutionE_TimBabych : 0.06766, 0.06784, 0.06963
solution_TimBabych : 0.07433, 0.07489, 0.07516
perm_sum_PM2R : 0.13143, 0.13175, 0.13179
rank_sum_PM2R : 0.14428, 0.14440, 0.14922
solution_python : 0.20072, 0.20076, 0.20084
ltree_count_PM2R : 0.20314, 0.20583, 0.24776
perm_radixI_PM2R : 0.23061, 0.23078, 0.23525
perm_radixR_PM2R : 0.23894, 0.23915, 0.24234
perm_fenwick_PM2R : 0.30984, 0.31181, 0.31503
fenwick_inline_PM2R : 0.31933, 0.32680, 0.32722
merge_count_BM : 0.36003, 0.36387, 0.36409
count_inversions_NiklasB : 0.36796, 0.36814, 0.37106
merge_PM2R : 0.36847, 0.36848, 0.37127
fenwick_PM2R : 0.37833, 0.37847, 0.38095
count_inversion_mkso : 0.42746, 0.42747, 0.43184
inv_cnt_ZheHu : 0.48969, 0.48974, 0.49293
reversePairs_nomanpouigt : 0.67791, 0.68157, 0.72420
bruteforce_loops_PM2R : 0.82816, 0.83175, 0.83282
bruteforce_sum_PM2R : 1.03322, 1.03378, 1.03562
Value: 6194
Size = 320, hi = 160, 64 loops
solutionE_TimBabych : 0.07467, 0.07470, 0.07483
solution_TimBabych : 0.08036, 0.08066, 0.08077
perm_sum_PM2R : 0.21142, 0.21201, 0.25766
solution_python : 0.22410, 0.22644, 0.22897
rank_sum_PM2R : 0.22820, 0.22851, 0.22877
ltree_count_PM2R : 0.24424, 0.24595, 0.24645
perm_radixI_PM2R : 0.25690, 0.25710, 0.26191
perm_radixR_PM2R : 0.26501, 0.26504, 0.26729
perm_fenwick_PM2R : 0.33483, 0.33507, 0.33845
fenwick_inline_PM2R : 0.34413, 0.34484, 0.35153
merge_count_BM : 0.39875, 0.39919, 0.40302
fenwick_PM2R : 0.40434, 0.40439, 0.40845
merge_PM2R : 0.40814, 0.41531, 0.51417
count_inversions_NiklasB : 0.41681, 0.42009, 0.42128
count_inversion_mkso : 0.47132, 0.47192, 0.47385
inv_cnt_ZheHu : 0.54468, 0.54750, 0.54893
reversePairs_nomanpouigt : 0.76164, 0.76389, 0.80357
bruteforce_loops_PM2R : 1.59125, 1.60430, 1.64131
bruteforce_sum_PM2R : 2.03734, 2.03834, 2.03975
Value: 24959
Run 2
Size = 640, hi = 320, 8 loops
solutionE_TimBabych : 0.04135, 0.04374, 0.04575
ltree_count_PM2R : 0.06738, 0.06758, 0.06874
perm_radixI_PM2R : 0.06928, 0.06943, 0.07019
fenwick_inline_PM2R : 0.07850, 0.07856, 0.08059
perm_fenwick_PM2R : 0.08151, 0.08162, 0.08170
perm_sum_PM2R : 0.09122, 0.09133, 0.09221
rank_sum_PM2R : 0.09549, 0.09603, 0.11270
merge_count_BM : 0.10733, 0.10807, 0.11032
count_inversions_NiklasB : 0.12460, 0.19865, 0.20205
solution_python : 0.13514, 0.13585, 0.13814
Size = 1280, hi = 640, 8 loops
solutionE_TimBabych : 0.04714, 0.04742, 0.04752
perm_radixI_PM2R : 0.15325, 0.15388, 0.15525
solution_python : 0.15709, 0.15715, 0.16076
fenwick_inline_PM2R : 0.16048, 0.16160, 0.16403
ltree_count_PM2R : 0.16213, 0.16238, 0.16428
perm_fenwick_PM2R : 0.16408, 0.16416, 0.16449
count_inversions_NiklasB : 0.19755, 0.19833, 0.19897
merge_count_BM : 0.23736, 0.23793, 0.23912
perm_sum_PM2R : 0.32946, 0.32969, 0.33277
rank_sum_PM2R : 0.34637, 0.34756, 0.34858
Size = 2560, hi = 1280, 8 loops
solutionE_TimBabych : 0.10898, 0.11005, 0.11025
perm_radixI_PM2R : 0.33345, 0.33352, 0.37656
ltree_count_PM2R : 0.34670, 0.34786, 0.34833
perm_fenwick_PM2R : 0.34816, 0.34879, 0.35214
fenwick_inline_PM2R : 0.36196, 0.36455, 0.36741
solution_python : 0.36498, 0.36637, 0.40887
count_inversions_NiklasB : 0.42274, 0.42745, 0.42995
merge_count_BM : 0.50799, 0.50898, 0.50917
perm_sum_PM2R : 1.27773, 1.27897, 1.27951
rank_sum_PM2R : 1.29728, 1.30389, 1.30448
Size = 5120, hi = 2560, 8 loops
solutionE_TimBabych : 0.26914, 0.26993, 0.27253
perm_radixI_PM2R : 0.71416, 0.71634, 0.71753
perm_fenwick_PM2R : 0.71976, 0.72078, 0.72078
fenwick_inline_PM2R : 0.72776, 0.72804, 0.73143
ltree_count_PM2R : 0.81972, 0.82043, 0.82290
solution_python : 0.83714, 0.83756, 0.83962
count_inversions_NiklasB : 0.87282, 0.87395, 0.92087
merge_count_BM : 1.09496, 1.09584, 1.10207
rank_sum_PM2R : 5.02564, 5.06277, 5.06666
perm_sum_PM2R : 5.09088, 5.12999, 5.13512
Size = 10240, hi = 5120, 8 loops
solutionE_TimBabych : 0.71556, 0.71718, 0.72201
perm_radixI_PM2R : 1.54785, 1.55096, 1.55515
perm_fenwick_PM2R : 1.55103, 1.55353, 1.59298
fenwick_inline_PM2R : 1.57118, 1.57240, 1.57271
ltree_count_PM2R : 1.76240, 1.76247, 1.80944
count_inversions_NiklasB : 1.86543, 1.86851, 1.87208
solution_python : 2.01490, 2.01519, 2.06423
merge_count_BM : 2.35215, 2.35301, 2.40023
rank_sum_PM2R : 20.07048, 20.08399, 20.13200
perm_sum_PM2R : 20.10187, 20.12551, 20.12683
Run 3
Size = 20480, hi = 10240, 4 loops
solutionE_TimBabych : 1.07636, 1.08243, 1.09569
perm_radixI_PM2R : 1.59579, 1.60519, 1.61785
perm_fenwick_PM2R : 1.66885, 1.68549, 1.71109
fenwick_inline_PM2R : 1.72073, 1.72752, 1.77217
ltree_count_PM2R : 1.96900, 1.97820, 2.02578
count_inversions_NiklasB : 2.03257, 2.05005, 2.18548
merge_count_BM : 2.46768, 2.47377, 2.52133
solution_python : 2.49833, 2.50179, 3.79819
Size = 40960, hi = 20480, 4 loops
solutionE_TimBabych : 3.51733, 3.52008, 3.56996
perm_radixI_PM2R : 3.51736, 3.52365, 3.56459
perm_fenwick_PM2R : 3.76097, 3.80900, 3.87974
fenwick_inline_PM2R : 3.95099, 3.96300, 3.99748
ltree_count_PM2R : 4.49866, 4.54652, 5.39716
count_inversions_NiklasB : 4.61851, 4.64303, 4.73026
merge_count_BM : 5.31945, 5.35378, 5.35951
solution_python : 6.78756, 6.82911, 6.98217
Size = 81920, hi = 40960, 4 loops
perm_radixI_PM2R : 7.68723, 7.71986, 7.72135
perm_fenwick_PM2R : 8.52404, 8.53349, 8.53710
fenwick_inline_PM2R : 8.97082, 8.97561, 8.98347
ltree_count_PM2R : 10.01142, 10.01426, 10.03216
count_inversions_NiklasB : 10.60807, 10.62424, 10.70425
merge_count_BM : 11.42149, 11.42342, 11.47003
solutionE_TimBabych : 12.83390, 12.83485, 12.89747
solution_python : 19.66092, 19.67067, 20.72204
Size = 163840, hi = 81920, 4 loops
perm_radixI_PM2R : 17.14153, 17.16885, 17.22240
perm_fenwick_PM2R : 19.25944, 19.27844, 20.27568
fenwick_inline_PM2R : 19.78221, 19.80219, 19.80766
ltree_count_PM2R : 22.42240, 22.43259, 22.48837
count_inversions_NiklasB : 22.97341, 23.01516, 23.98052
merge_count_BM : 24.42683, 24.48559, 24.51488
solutionE_TimBabych : 60.96006, 61.20145, 63.71835
solution_python : 73.75132, 73.79854, 73.95874
Size = 327680, hi = 163840, 4 loops
perm_radixI_PM2R : 36.56715, 36.60221, 37.05071
perm_fenwick_PM2R : 42.21616, 42.21838, 42.26053
fenwick_inline_PM2R : 43.04987, 43.09075, 43.13287
ltree_count_PM2R : 49.87400, 50.08509, 50.69292
count_inversions_NiklasB : 50.74591, 50.75012, 50.75551
merge_count_BM : 52.37284, 52.51491, 53.43003
solutionE_TimBabych : 373.67198, 377.03341, 377.42360
solution_python : 411.69178, 411.92691, 412.83856
Size = 655360, hi = 327680, 4 loops
perm_radixI_PM2R : 78.51927, 78.66327, 79.46325
perm_fenwick_PM2R : 90.64711, 90.80328, 91.76126
fenwick_inline_PM2R : 93.32482, 93.39086, 94.28880
count_inversions_NiklasB : 107.74393, 107.80036, 108.71443
ltree_count_PM2R : 109.11328, 109.23592, 110.18247
merge_count_BM : 111.05633, 111.07840, 112.05861
solutionE_TimBabych : 1830.46443, 1836.39960, 1849.53918
solution_python : 1911.03692, 1912.04484, 1914.69786
public static int mergeSort(int[] a, int p, int r)
{
int countInversion = 0;
if(p < r)
{
int q = (p + r)/2;
countInversion = mergeSort(a, p, q);
countInversion += mergeSort(a, q+1, r);
countInversion += merge(a, p, q, r);
}
return countInversion;
}
public static int merge(int[] a, int p, int q, int r)
{
//p=0, q=1, r=3
int countingInversion = 0;
int n1 = q-p+1;
int n2 = r-q;
int[] temp1 = new int[n1+1];
int[] temp2 = new int[n2+1];
for(int i=0; i<n1; i++) temp1[i] = a[p+i];
for(int i=0; i<n2; i++) temp2[i] = a[q+1+i];
temp1[n1] = Integer.MAX_VALUE;
temp2[n2] = Integer.MAX_VALUE;
int i = 0, j = 0;
for(int k=p; k<=r; k++)
{
if(temp1[i] <= temp2[j])
{
a[k] = temp1[i];
i++;
}
else
{
a[k] = temp2[j];
j++;
countingInversion=countingInversion+(n1-i);
}
}
return countingInversion;
}
public static void main(String[] args)
{
int[] a = {1, 20, 6, 4, 5};
int countInversion = mergeSort(a, 0, a.length-1);
System.out.println(countInversion);
}
Другое решение Python, короткое. Использует встроенный модуль bisect, который предоставляет функции для вставки элемента на его место в отсортированном массиве и для поиска индекса элемента в отсортированном массиве.
Идея состоит в том, чтобы хранить элементы слева от n-го в таком массиве, что позволило бы нам легко найти их число больше n-го.
import bisect
def solution(A):
sorted_left = []
res = 0
for i in xrange(1, len(A)):
bisect.insort_left(sorted_left, A[i-1])
# i is also the length of sorted_left
res += (i - bisect.bisect(sorted_left, A[i]))
return res
Так как это старый вопрос, я предоставлю свой ответ на C.
#include <stdio.h>
int count = 0;
int inversions(int a[], int len);
void mergesort(int a[], int left, int right);
void merge(int a[], int left, int mid, int right);
int main() {
int a[] = { 1, 5, 2, 4, 0 };
printf("%d\n", inversions(a, 5));
}
int inversions(int a[], int len) {
mergesort(a, 0, len - 1);
return count;
}
void mergesort(int a[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergesort(a, left, mid);
mergesort(a, mid + 1, right);
merge(a, left, mid, right);
}
}
void merge(int a[], int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = 0;
int b[right - left + 1];
while (i <= mid && j <= right) {
if (a[i] <= a[j]) {
b[k++] = a[i++];
} else {
printf("right element: %d\n", a[j]);
count += (mid - i + 1);
printf("new count: %d\n", count);
b[k++] = a[j++];
}
}
while (i <= mid)
b[k++] = a[i++];
while (j <= right)
b[k++] = a[j++];
for (i = left, k = 0; i <= right; i++, k++) {
a[i] = b[k];
}
}
Большинство ответов основаны на MergeSort но это не единственный способ решить эту проблему - O(nlogn)
Обсуду несколько подходов.
Использовать
Balanced Binary Search Tree- Расширьте свое дерево, чтобы сохранить частоты для повторяющихся элементов.
- Идея состоит в том, чтобы продолжать подсчет больших узлов при переходе дерева от корня к листу для вставки.
Что-то вроде этого.
Node *insert(Node* root, int data, int& count){
if(!root) return new Node(data);
if(root->data == data){
root->freq++;
count += getSize(root->right);
}
else if(root->data > data){
count += getSize(root->right) + root->freq;
root->left = insert(root->left, data, count);
}
else root->right = insert(root->right, data, count);
return balance(root);
}
int getCount(int *a, int n){
int c = 0;
Node *root = NULL;
for(auto i=0; i<n; i++) root = insert(root, a[i], c);
return c;
}
- Использовать
Binary Indexed Tree- Создайте суммирующий BIT.
- Выполните цикл с конца и начните подсчет больших элементов.
int getInversions(int[] a) {
int n = a.length, inversions = 0;
int[] bit = new int[n+1];
compress(a);
BIT b = new BIT();
for (int i=n-1; i>=0; i--) {
inversions += b.getSum(bit, a[i] - 1);
b.update(bit, n, a[i], 1);
}
return inversions;
}
- Использовать
Segment Tree- Создайте дерево сегментов суммирования.
- Цикл от конца массива и запрос между
[0, a[i]-1]и обновитьa[i] with 1
int getInversions(int *a, int n) {
int N = n + 1, c = 0;
compress(a, n);
int tree[N<<1] = {0};
for (int i=n-1; i>=0; i--) {
c+= query(tree, N, 0, a[i] - 1);
update(tree, N, a[i], 1);
}
return c;
}
Также при использовании BIT или Segment-Tree хорошая идея сделать Coordinate compression
void compress(int *a, int n) {
int temp[n];
for (int i=0; i<n; i++) temp[i] = a[i];
sort(temp, temp+n);
for (int i=0; i<n; i++) a[i] = lower_bound(temp, temp+n, a[i]) - temp + 1;
}
Вот решение C++
/**
*array sorting needed to verify if first arrays n'th element is greater than sencond arrays
*some element then all elements following n will do the same
*/
#include<stdio.h>
#include<iostream>
using namespace std;
int countInversions(int array[],int size);
int merge(int arr1[],int size1,int arr2[],int size2,int[]);
int main()
{
int array[] = {2, 4, 1, 3, 5};
int size = sizeof(array) / sizeof(array[0]);
int x = countInversions(array,size);
printf("number of inversions = %d",x);
}
int countInversions(int array[],int size)
{
if(size > 1 )
{
int mid = size / 2;
int count1 = countInversions(array,mid);
int count2 = countInversions(array+mid,size-mid);
int temp[size];
int count3 = merge(array,mid,array+mid,size-mid,temp);
for(int x =0;x<size ;x++)
{
array[x] = temp[x];
}
return count1 + count2 + count3;
}else{
return 0;
}
}
int merge(int arr1[],int size1,int arr2[],int size2,int temp[])
{
int count = 0;
int a = 0;
int b = 0;
int c = 0;
while(a < size1 && b < size2)
{
if(arr1[a] < arr2[b])
{
temp[c] = arr1[a];
c++;
a++;
}else{
temp[c] = arr2[b];
b++;
c++;
count = count + size1 -a;
}
}
while(a < size1)
{
temp[c] = arr1[a];
c++;a++;
}
while(b < size2)
{
temp[c] = arr2[b];
c++;b++;
}
return count;
}
Ну, у меня есть другое решение, но я боюсь, что это будет работать только для отдельных элементов массива.
//Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i,n;
cin >> n;
int arr[n],inv[n];
for(i=0;i<n;i++){
cin >> arr[i];
}
vector<int> v;
v.push_back(arr[n-1]);
inv[n-1]=0;
for(i=n-2;i>=0;i--){
auto it = lower_bound(v.begin(),v.end(),arr[i]);
//calculating least element in vector v which is greater than arr[i]
inv[i]=it-v.begin();
//calculating distance from starting of vector
v.insert(it,arr[i]);
//inserting that element into vector v
}
for(i=0;i<n;i++){
cout << inv[i] << " ";
}
cout << endl;
return 0;
}
Чтобы объяснить мой код, мы продолжаем добавлять элементы с конца Array. Для любого входящего элемента массива мы находим индекс первого элемента в векторе v, который больше, чем наш входящий элемент, и присваиваем это значение счетчику инверсий индекса входящего элемента. После этого мы вставляем этот элемент в вектор v в его правильном положении, чтобы вектор v оставался в отсортированном порядке.
//INPUT
4
2 1 4 3
//OUTPUT
1 0 1 0
//To calculate total inversion count just add up all the elements in output array
Вот код C для подсчета инверсий
#include <stdio.h>
#include <stdlib.h>
int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);
/* This function sorts the input array and returns the
number of inversions in the array */
int mergeSort(int arr[], int array_size)
{
int *temp = (int *)malloc(sizeof(int)*array_size);
return _mergeSort(arr, temp, 0, array_size - 1);
}
/* An auxiliary recursive function that sorts the input array and
returns the number of inversions in the array. */
int _mergeSort(int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right > left)
{
/* Divide the array into two parts and call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left)/2;
/* Inversion count will be sum of inversions in left-part, right-part
and number of inversions in merging */
inv_count = _mergeSort(arr, temp, left, mid);
inv_count += _mergeSort(arr, temp, mid+1, right);
/*Merge the two parts*/
inv_count += merge(arr, temp, left, mid+1, right);
}
return inv_count;
}
/* This funt merges two sorted arrays and returns inversion count in
the arrays.*/
int merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;
i = left; /* i is index for left subarray*/
j = mid; /* i is index for right subarray*/
k = left; /* i is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
/*this is tricky -- see above explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}
/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];
/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];
/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];
return inv_count;
}
/* Driver progra to test above functions */
int main(int argv, char** args)
{
int arr[] = {1, 20, 6, 4, 5};
printf(" Number of inversions are %d \n", mergeSort(arr, 5));
getchar();
return 0;
}
Подробное объяснение было дано здесь: http://www.geeksforgeeks.org/counting-inversions/
Вот O(n*log(n)) реализация Perl:
sub sort_and_count {
my ($arr, $n) = @_;
return ($arr, 0) unless $n > 1;
my $mid = $n % 2 == 1 ? ($n-1)/2 : $n/2;
my @left = @$arr[0..$mid-1];
my @right = @$arr[$mid..$n-1];
my ($sleft, $x) = sort_and_count( \@left, $mid );
my ($sright, $y) = sort_and_count( \@right, $n-$mid);
my ($merged, $z) = merge_and_countsplitinv( $sleft, $sright, $n );
return ($merged, $x+$y+$z);
}
sub merge_and_countsplitinv {
my ($left, $right, $n) = @_;
my ($l_c, $r_c) = ($#$left+1, $#$right+1);
my ($i, $j) = (0, 0);
my @merged;
my $inv = 0;
for my $k (0..$n-1) {
if ($i<$l_c && $j<$r_c) {
if ( $left->[$i] < $right->[$j]) {
push @merged, $left->[$i];
$i+=1;
} else {
push @merged, $right->[$j];
$j+=1;
$inv += $l_c - $i;
}
} else {
if ($i>=$l_c) {
push @merged, @$right[ $j..$#$right ];
} else {
push @merged, @$left[ $i..$#$left ];
}
last;
}
}
return (\@merged, $inv);
}
Простой ответ O(n^2) - использовать вложенные циклы for и увеличивать счетчик для каждой инверсии.
int counter = 0;
for(int i = 0; i < n - 1; i++)
{
for(int j = i+1; j < n; j++)
{
if( A[i] > A[j] )
{
counter++;
}
}
}
return counter;
Теперь я думаю, что вы хотите более эффективное решение, я подумаю об этом.
O(n log n) время, O(n) пространственное решение в Java.
Сортировка слиянием с настройкой для сохранения количества инверсий, выполненных на этапе объединения. (для хорошо объясненного слияния взгляните на http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html)
Поскольку сортировка слиянием может быть выполнена на месте, сложность пространства может быть улучшена до O(1).
При использовании этого вида инверсии происходят только на этапе слияния и только тогда, когда мы должны поместить элемент второй части перед элементами из первой половины, например
- 0 5 10 15
объединены с
- 1 6 22
у нас 3 + 2 + 0 = 5 инверсий:
- 1 с {5, 10, 15}
- 6 с {10, 15}
- 22 с {}
После того, как мы сделали 5 инверсий, наш новый объединенный список - 0, 1, 5, 6, 10, 15, 22
На Codility есть демонстрационная задача ArrayInversionCount, где вы можете протестировать свое решение.
public class FindInversions {
public static int solution(int[] input) {
if (input == null)
return 0;
int[] helper = new int[input.length];
return mergeSort(0, input.length - 1, input, helper);
}
public static int mergeSort(int low, int high, int[] input, int[] helper) {
int inversionCount = 0;
if (low < high) {
int medium = low + (high - low) / 2;
inversionCount += mergeSort(low, medium, input, helper);
inversionCount += mergeSort(medium + 1, high, input, helper);
inversionCount += merge(low, medium, high, input, helper);
}
return inversionCount;
}
public static int merge(int low, int medium, int high, int[] input, int[] helper) {
int inversionCount = 0;
for (int i = low; i <= high; i++)
helper[i] = input[i];
int i = low;
int j = medium + 1;
int k = low;
while (i <= medium && j <= high) {
if (helper[i] <= helper[j]) {
input[k] = helper[i];
i++;
} else {
input[k] = helper[j];
// the number of elements in the first half which the j element needs to jump over.
// there is an inversion between each of those elements and j.
inversionCount += (medium + 1 - i);
j++;
}
k++;
}
// finish writing back in the input the elements from the first part
while (i <= medium) {
input[k] = helper[i];
i++;
k++;
}
return inversionCount;
}
}
Мой ответ на Python:
1- Сортируйте массив в первую очередь и сделайте его копию. В моей программе B представляет отсортированный массив. 2. Переберите исходный массив (не отсортированный) и найдите индекс этого элемента в отсортированном списке. Также запишите индекс элемента. 3. Убедитесь, что у элемента нет дубликатов, если он есть, вам нужно изменить значение индекса на -1. Условие while в моей программе точно так и делает. 4. Продолжайте считать инверсию, которая будет вашим значением индекса, и удалите элемент, как только вы вычислили его инверсию.
def binarySearch(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last)//2
if alist[midpoint] == item:
return midpoint
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1
def solution(A):
B = list(A)
B.sort()
inversion_count = 0
for i in range(len(A)):
j = binarySearch(B, A[i])
while B[j] == B[j - 1]:
if j < 1:
break
j -= 1
inversion_count += j
B.pop(j)
if inversion_count > 1000000000:
return -1
else:
return inversion_count
print solution([4, 10, 11, 1, 3, 9, 10])
Одним из возможных решений в C++, удовлетворяющих требованию сложности времени O(N*log(N)), было бы следующее.
#include <algorithm>
vector<int> merge(vector<int>left, vector<int>right, int &counter)
{
vector<int> result;
vector<int>::iterator it_l=left.begin();
vector<int>::iterator it_r=right.begin();
int index_left=0;
while(it_l!=left.end() || it_r!=right.end())
{
// the following is true if we are finished with the left vector
// OR if the value in the right vector is the smaller one.
if(it_l==left.end() || (it_r!=right.end() && *it_r<*it_l) )
{
result.push_back(*it_r);
it_r++;
// increase inversion counter
counter+=left.size()-index_left;
}
else
{
result.push_back(*it_l);
it_l++;
index_left++;
}
}
return result;
}
vector<int> merge_sort_and_count(vector<int> A, int &counter)
{
int N=A.size();
if(N==1)return A;
vector<int> left(A.begin(),A.begin()+N/2);
vector<int> right(A.begin()+N/2,A.end());
left=merge_sort_and_count(left,counter);
right=merge_sort_and_count(right,counter);
return merge(left, right, counter);
}
Отличается от обычной сортировки слиянием только счетчиком.
Я думаю, что ответ el diablo можно оптимизировать, чтобы удалить шаг 2b, на котором мы удаляем уже обработанные элементы.
Вместо этого мы можем определить
# инверсии для x = положение x в отсортированном массиве - положение x в массиве orig
Реализация на python3 ответа user27884 user187241 с временной сложностью O(N*log(N)) и общей оценкой 100% по Codility:
def solution(A):
B = A.copy()
B.sort()
numInversions = 0
maxNumInversions = 1000000000
for num in A:
posInSorted = binarySearch(B, num)
duplicatesLessThanNum = getDuplicatesLessThanNum(num, B, posInSorted)
numInversions += posInSorted - duplicatesLessThanNum
if numInversions > maxNumInversions:
return -1
del B[posInSorted]
return numInversions
def getDuplicatesLessThanNum(num, arr, pos):
numDuplicates = 0
while pos > 0 and arr[pos] == num:
pos -= 1
if arr[pos] == num:
numDuplicates += 1
return numDuplicates
def binarySearch(B, num):
low = 0
high = len(B) - 1
while low <= high:
mid = (high + low)//2
if B[mid] < num:
low = mid + 1
elif B[mid] > num:
high = mid - 1
else:
return mid
return -1
Максимально возможное количество инверсий для списка размеров n может быть обобщено выражением:
maxPossibleInversions = (n * (n-1) ) / 2
Так что для массива размера 6 максимально возможные инверсии будут равны 15,
Для достижения сложности n logn мы могли бы добавить алгоритм инверсии для сортировки слиянием.
Вот обобщенные шаги:
- Разделить массив на две части
- Вызовите процедуру mergeSort. Если элемент в левом подмассиве больше, чем элемент в правом подмассиве, то make
inversionCount += leftSubArray.length
Это оно!
Это простой пример, который я сделал с использованием Javascript:
var arr = [6,5,4,3,2,1]; // Sample input array
var inversionCount = 0;
function mergeSort(arr) {
if(arr.length == 1)
return arr;
if(arr.length > 1) {
let breakpoint = Math.ceil((arr.length/2));
// Left list starts with 0, breakpoint-1
let leftList = arr.slice(0,breakpoint);
// Right list starts with breakpoint, length-1
let rightList = arr.slice(breakpoint,arr.length);
// Make a recursive call
leftList = mergeSort(leftList);
rightList = mergeSort(rightList);
var a = merge(leftList,rightList);
return a;
}
}
function merge(leftList,rightList) {
let result = [];
while(leftList.length && rightList.length) {
/**
* The shift() method removes the first element from an array
* and returns that element. This method changes the length
* of the array.
*/
if(leftList[0] <= rightList[0]) {
result.push(leftList.shift());
}else{
inversionCount += leftList.length;
result.push(rightList.shift());
}
}
while(leftList.length)
result.push(leftList.shift());
while(rightList.length)
result.push(rightList.shift());
console.log(result);
return result;
}
mergeSort(arr);
console.log('Number of inversions: ' + inversionCount);
Реализация подсчета инверсий в массиве с сортировкой слиянием в Swift:
Обратите внимание, что количество свопов увеличивается на
nSwaps += mid + 1 - iL
(это относительная длина левой части массива минус индекс текущего элемента в левой части)
... потому что это количество элементов, которые элемент в правой части массива должен был пропустить (число инверсий), чтобы стать отсортированными.
func merge(arr: inout [Int], arr2: inout [Int], low: Int, mid: Int, high: Int) -> Int {
var nSwaps = 0;
var i = low;
var iL = low;
var iR = mid + 1;
while iL <= mid && iR <= high {
if arr2[iL] <= arr2[iR] {
arr[i] = arr2[iL]
iL += 1
i += 1
} else {
arr[i] = arr2[iR]
nSwaps += mid + 1 - iL
iR += 1
i += 1
}
}
while iL <= mid {
arr[i] = arr2[iL]
iL += 1
i += 1
}
while iR <= high {
arr[i] = arr2[iR]
iR += 1
i += 1
}
return nSwaps
}
func mergeSort(arr: inout [Int]) -> Int {
var arr2 = arr
let nSwaps = mergeSort(arr: &arr, arr2: &arr2, low: 0, high: arr.count-1)
return nSwaps
}
func mergeSort(arr: inout [Int], arr2: inout [Int], low: Int, high: Int) -> Int {
if low >= high {
return 0
}
let mid = low + ((high - low) / 2)
var nSwaps = 0;
nSwaps += mergeSort(arr: &arr2, arr2: &arr, low: low, high: mid)
nSwaps += mergeSort(arr: &arr2, arr2: &arr, low: mid+1, high: high)
nSwaps += merge(arr: &arr, arr2: &arr2, low: low, mid: mid, high: high)
return nSwaps
}
var arrayToSort: [Int] = [2, 1, 3, 1, 2]
let nSwaps = mergeSort(arr: &arrayToSort)
print(arrayToSort) // [1, 1, 2, 2, 3]
print(nSwaps) // 4
Лучшим оптимизированным способом будет решение этой проблемы с помощью сортировки слиянием, где при слиянии мы можем проверить, сколько инверсий требуется, сравнивая левый и правый массив. Когда элемент в левом массиве больше, чем элемент в правом массиве, это будет инверсия.
Подход сортировки слиянием:-
Вот код Код точно такой же, как сортировка слиянием, за исключением фрагмента кода под mergeToParent метод, в котором я считаю инверсию в другом состоянии (left[leftunPicked] < right[rightunPicked])
public class TestInversionThruMergeSort {
static int count =0;
public static void main(String[] args) {
int[] arr = {6, 9, 1, 14, 8, 12, 3, 2};
partition(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
System.out.println("inversions are "+count);
}
public static void partition(int[] arr) {
if (arr.length > 1) {
int mid = (arr.length) / 2;
int[] left = null;
if (mid > 0) {
left = new int[mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
}
int[] right = new int[arr.length - left.length];
if ((arr.length - left.length) > 0) {
int j = 0;
for (int i = mid; i < arr.length; i++) {
right[j] = arr[i];
++j;
}
}
partition(left);
partition(right);
mergeToParent(left, right, arr);
}
}
public static void mergeToParent(int[] left, int[] right, int[] parent) {
int leftunPicked = 0;
int rightunPicked = 0;
int parentIndex = -1;
while (rightunPicked < right.length && leftunPicked < left.length) {
if (left[leftunPicked] < right[rightunPicked]) {
parent[++parentIndex] = left[leftunPicked];
++leftunPicked;
} else {
count = count + left.length-leftunPicked;
if ((rightunPicked < right.length)) {
parent[++parentIndex] = right[rightunPicked];
++rightunPicked;
}
}
}
while (leftunPicked < left.length) {
parent[++parentIndex] = left[leftunPicked];
++leftunPicked;
}
while (rightunPicked < right.length) {
parent[++parentIndex] = right[rightunPicked];
++rightunPicked;
}
}
}
Другой подход, в котором мы можем сравнить входной массив с отсортированным массивом:- Это реализация ответа Diablo. Хотя это не должно быть предпочтительным подходом, так как удаление n элементов из массива или списка - это log(n^2).
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
public class TestInversion {
public static void main(String[] args) {
Integer [] arr1 = {6, 9, 1, 14, 8, 12, 3, 2};
List<Integer> arr = new ArrayList(Arrays.asList(arr1));
List<Integer> sortArr = new ArrayList<Integer>();
for(int i=0;i<arr.size();i++){
sortArr.add(arr.get(i));
}
Collections.sort(sortArr);
int inversion = 0;
Iterator<Integer> iter = arr.iterator();
while(iter.hasNext()){
Integer el = (Integer)iter.next();
int index = sortArr.indexOf(el);
if(index+1 > 1){
inversion = inversion + ((index+1)-1);
}
//iter.remove();
sortArr.remove(el);
}
System.out.println("Inversions are "+inversion);
}
}
Вот мое решение O(n log n) в Ruby:
def solution(t)
sorted, inversion_count = sort_inversion_count(t)
return inversion_count
end
def sort_inversion_count(t)
midpoint = t.length / 2
left_half = t[0...midpoint]
right_half = t[midpoint..t.length]
if midpoint == 0
return t, 0
end
sorted_left_half, left_half_inversion_count = sort_inversion_count(left_half)
sorted_right_half, right_half_inversion_count = sort_inversion_count(right_half)
sorted = []
inversion_count = 0
while sorted_left_half.length > 0 or sorted_right_half.length > 0
if sorted_left_half.empty?
sorted.push sorted_right_half.shift
elsif sorted_right_half.empty?
sorted.push sorted_left_half.shift
else
if sorted_left_half[0] > sorted_right_half[0]
inversion_count += sorted_left_half.length
sorted.push sorted_right_half.shift
else
sorted.push sorted_left_half.shift
end
end
end
return sorted, inversion_count + left_half_inversion_count + right_half_inversion_count
end
И несколько тестовых случаев:
require "minitest/autorun"
class TestCodility < Minitest::Test
def test_given_example
a = [-1, 6, 3, 4, 7, 4]
assert_equal solution(a), 4
end
def test_empty
a = []
assert_equal solution(a), 0
end
def test_singleton
a = [0]
assert_equal solution(a), 0
end
def test_none
a = [1,2,3,4,5,6,7]
assert_equal solution(a), 0
end
def test_all
a = [5,4,3,2,1]
assert_equal solution(a), 10
end
def test_clones
a = [4,4,4,4,4,4]
assert_equal solution(a), 0
end
end