Количество инверсий в перестановке
Инверсии в комбинаторике – это количество пар элементов, в которых следующий элемент имеет меньший номер, чем предыдущий. Иногда важно иметь количественную оценку степени отличия произвольной перестановки от лексиграфически наименьшей по числу нарушений возрастающего порядка значений ее элементов. Любая пара элементов, где имеет место такое нарушение их взаимного положения в перестановке, называется инверсией.
Инверсии перестановок
Для компактной записи инверсий по элементам перестановки применяются вектор инверсий (V 1,…V j,…V n) и таблица инверсий (W 1,…W j,…W n). Эти обе формы записи идентифицируют числа инверсий для всех элементов перестановки.
Состав вектора и таблицы инверсий для цифровой перестановки P=(5,9,1,8,2,6,4,7,3) показан в следующем примере, где для наглядности индексированы позиции всех элементов:
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | pj | 5 | 9 | 1 | 8 | 2 | 6 | 4 | 7 | 3 | Vj | 0 | 0 | 2 | 1 | 3 | 2 | 4 | 2 | 6 | Wj | 2 | 3 | 6 | 4 | 0 | 2 | 2 | 1 | 9 |
В частности, в этом примере V 8=2, потому что слева от элемента P 8=7 в перестановке есть 2 элемента P 2=9 и P 4=8 с большим значением, чем 7. С другой стороны, W 8=1,потому что слева от элемента со значением 8 (это P 4) в перестановке имеется только 1 элемент (P 2=9), значение которого больше, чем 8. Аналогичным образом можно обосновать выбор величин остальных компонентов вектора и таблицы инверсий в данном примере. Следует также отметить, что для любой перестановки значения компонентов вектора и таблицы инверсий связаны следующими соотношениями:
Возвращаясь к интегральным оценкам, следует отметить, что сумма значений всех компонентов вектора или таблицы инверсий определяет общее число инверсий I перестановки. В частности, для рассмотренного примера оно равно 20:
вычисление количества «инверсий» в перестановке
4 ответа
Вы можете использовать алгоритм сортировки слиянием.
В цикле алгоритма слияния левая и правая половины отсортированы по возрастанию, и мы хотим объединить их в один отсортированный массив. Обратите внимание, что все элементы в правой части имеют более высокие индексы, чем элементы в левой части.
Это оригинальные алгоритмы MERGE и MERGE-SORT от Cormen, Leiserson, Rivest, Stein Introduction to Algorithms:
В строках 8 и 9 в MERGE infinity находится так называемая сигнальная карта, значение которой таково, что все элементы массива меньше ее. Чтобы получить число инверсий, можно ввести глобальный счетчик, скажем, ninv инициализирован нулем перед вызовом MERGE-SORT, а затем изменить алгоритм MERGE, добавив одну строку в операторе else после строки 16, что-то вроде
Чем после завершения MERGE-SORT ninv будет удерживать количество инверсий
В 2010 году в SIAM опубликована статья Чама и Патраску под названием Подсчет инверсий, Автономный подсчет ортогональных диапазонов и связанные проблемы, который дает алгоритм, занимающий время O (n sqrt (log (n))). В настоящее время это наиболее известный алгоритм, улучшающий давно существующий алгоритм O (n log (n) / log (log (n))). Из аннотации:
Наша новая техника довольно проста: мы выполняем «вертикальное разбиение» дерева (сродни деревьям ван Эмде Боаса) и используем идеи из внешней памяти. Однако методика находит множество приложений: например, мы получаем
Два указателя, сортировка слиянием¶
Количество пар с разницей, больше чем K¶
А можно ли быстрее?
Это называется метод двух указателей — так как мы двигаем два указателя first и second одновременно слева направо по каким-то правилам. Обычно его используют на одном отсортированном массиве.
Давайте разберем еще примеры.
Максимальная разница, но не больше K¶
Три массива¶
Чаще всего метод двух указателей применяют к одному отсортированному массиву. Но иногда можно применить его и на несколько, например, три массива.
Так что мы просто сдвигаем каждый раз указатель на минимум из трех элементов, если есть куда его двигать, иначе заканчиваем. Каждый раз обновляем ответ. Так мы переберем всех разумные тройки элементов.
Слияние¶
Еще пример двух указателей на нескольких массивах.
Пусть первый указатель будет указывать на начало первого массива, а второй, соответственно, на начало второго. Из двух текущих элементов, на которые указывают указатели, выберем наименьший и положим на соответствующую позицию в новом массиве, после чего сдвинем указатель. Продолжим этот процесс пока в обоих массивах не закончатся элементы. Тогда код будет выглядеть следующим образом:
Сортировка слиянием¶
Пусть у нас есть какой-то массив.
Так сколько же работает это решение?
Количество инверсий¶
Найти количество инверсий в данной перестановке.
Заметим, что мы уже знаем количество инверсий в левой половине и в правой половине массива. Осталось лишь посчитать число инверсий, где одно число лежит в левой половине, а второе в правой половине. Как же их посчитать?
Давайте подробнее рассмотрим операцию merge левой и правой половины (которую мы ранее заменили на вызов встроенной функции merge). Первый указатель указывает на элемент левой половины, второй указатель указывает на элемент второй половины, мы смотрим на минимум из них и этот указатель вдигаем вправо.
Как посчитать количество инверсий в перестановке
Да да, Вы безусловно правы. Там нужно писать в восьмой строке НОВЫЙ[j]:=ложь по причине, которой Вы сами огласили.
Только получается, что цикл будет исполняться на k раз, а k-1, т.к. в шестой строке мы обрабатываем первую вершину цикла, а все последующие k-1 вершины в рамках цикла while.
К сожалению опечатки прокрадываются даже в такие шедевральные издания.
Если же мы фиксируем размер корзинки, то количество корзинок пропорционально N, и цикл подсчёта суммы длин корзинок (в версии из видео) или цикл инкремента кэша инверсий (в версии с everfall) даёт O(N), что в итого даст квадрат. В версии из видео можно сумму считать на дереве Фенвика, тогда получится O(log(N)) тело цикла и O(N*log(N)) итого. Но не более.
1. По поводу подсчета количества инверсий с помощью карманной сортировки.
Вы не спорите, что карманная сортировка работает за O(N). Давайте вспомним, что там происходит:
a) Все элементы раскидываются по карманам.
b) Каждый карман сортируется сортировкой вставками.
Фиксируем количество карманов(константа С). Размер кармана пропорционален N, то тогда получается по Вашим доводам сортировка кармана работает за O(N*N), т.к. п.b) будет работать именно с такой сложностью. Итого общее время работы С*O(N*N). В Кормене(второе издание с.230-234) описываются мат. выкладки, доказывающие линейность карманной сортировки.
Что касается инверсий, то по сути дела в приведенной реализации происходит карманная сортировка в online режиме и вся мат.часть из Кормена подходит и под этот случай.
2. Не совсем понял конец фразы «В версии из видео можно сумму считать на дереве Фенвика, тогда получится O(log(N)) тело цикла и O(N*log(N)) итого. Но не более.»
3. Пробовать на 100.000 элементов я не стал.
Изначально задача формулировалась для 10.000 элементов, собственно поэтому и родилась идея попробовать все три метода. 100.000 элементов лучше решать Фенвиком.
P.S: Напомню, что по условию задачи мы имеем дело с перестановкой, поэтому при использовании карманной сортировки все карманы забиваются равномерно. Идеально подходит случай, когда количество карманов равно количеству элементов внутри кармана. Т.е. случай когда количество карманов = sqrt(N). Для случая в 10.000 элементов размер кармана в 100 раз меньше размера всей коллекции, поэтому можно условно считать, что сортировка кармана выполняется за большую константу.
Прочитал выкладки из Кормена, которые, впрочем, полностью повторяют русскую Википедию, проникся.
И вот с этого места мне стало казаться, что это не N.
Что вы думаете по этому поводу? Я уже понял (хотя и не понял, почему, так что, скорее поверил), что лучший случай, когда размер корзинки равен количеству корзинок. А для 100 000 лучше 100 корзинок по 1000, 1000 корзинок по 100 или 316 корзинок по примерно 317?
Карманная сортировка имеет скорее академический интерес. Работает с очень большой константой и при условии равномерного распределения значений внутри сортируемого массива.
Что касается выбора размера кармана(он же корзинка).
Тут следующие соображения:
Короче говоря все свелось к классической школьной задаче: Нужно найти отношение сторон прямоугольника с фиксированной площадью, так чтобы его периметр был минимальным. Данное условие достигается, когда стороны относятся как 1:1. Так и в нашем случае С должно быть равно M.
Таблица инверсий
Содержание
Алгоритм построения за O(N 2 ) [ править ]
Таблицу инверсий тривиально построить по определению. Для каждого элемента перестановки считаем количество элементов, больших данного и стоящих в перестановке левее него. Алгоритм построения в псевдокоде выглядит так:
Алгоритм построения за O(N log N) [ править ]
Пусть дано разбиение перестановки на два списка, причём для каждого элемента дано число инверсий слева с элементами того же списка и известно, что все числа первого списка стоят левее всех чисел второго списка в исходной перестановке. Будем считать количество инверсий слева элементов обоих списков следующим образом: сливаем списки, аналогично сортировке слиянием.
Если в результат нужно записать элемент первого списка, то все нерассмотренные элементы второго списка больше, следовательно, количество инверсий для этого элемента не меняется. Если в результат нужно записать элемент второго списка, то все нерассмотренные элементы первого списка больше его и стоят левее. Следовательно, количество инверсий для этого элемента следует увеличить на количество нерассмотренных элементов первого списка.
Описанный алгоритм записывается в псевдокод следующим образом:
Алгоритм построения за O(N) [ править ]
В разделе карманная сортировка доказывается, что она работает за линейное время. Что касается подсчета инверсий, то в приведенной реализации происходит карманная сортировка в online режиме и вся математическая часть подходит и под этот случай.
Алгоритм восстановления [ править ]
Этот простой алгоритм имеет сложность [math]O(n^2)[/math] — внутренний цикл делает до [math]n[/math] итераций, внешний — ровно [math]n[/math] итераций.
Данный алгоритм переписывается в код следующим образом:
Пример [ править ]
| (5, 0) | (7, 0) | (1, 0) | (3, 0) | (4, 0) | (6, 0) | (8, 0) | (2, 0) |
| (5, 0), (7, 0) | (1, 0), (3, 0) | (4, 0), (6, 0) | (2, 1), (8, 0) | ||||
| (1, 2), (3, 2), (5, 0), (7, 0) | (2, 3), (4, 0), (6, 0), (8, 0) | ||||||
| (1, 2), (2, 6), (3, 2), (4, 2), (5, 0), (6, 1), (7, 0), (8, 0) | |||||||