Слияние двух частичных (совместно переопределенных) наборов информации о заказе

Допустим, у нас есть столбцы C, пронумерованные от 1 до C. У нас есть две последовательности последовательностей столбцов: U = u₁, u₂, ... u_n и S = s₁, s₂, ... s_m. Мы хотим найти перестановку P для S, такую, что P не имеет инверсий относительно U и минимальное количество инверсий относительно S.

Мы можем показать, что существует такой оптимальный P, который представляет собой чередование U ∩ S и S \ U. Под «чередованием» я подразумеваю, что P не имеет инверсий относительно U ∩ S или S \ U.

Мы можем применить динамическое программирование, чтобы найти оптимальное чередование: Пусть A = (a_{i< /sub>) = U ∩ S и B = (bj) = S \ U. Пусть f(i,j) — количество инверсий относительно S оптимального чередования префиксов a1...i слова A и b1...j слова B. Идея заключается в следующем. очень похоже на алгоритм самой длинной общей подпоследовательности DP. у нас рецидив}

f(0,j) = 0 for all j >= 0
f(i,0) = f(i-1, 0) + sum(k=1 to i-1, [1 if A[i] appears before A[k] in S])
f(i,j) = min(f(i-1, j) + sum(k=1 to i-1, [1 if A[i] appears before A[k] in S])
                       + sum(k=1 to j, [1 if A[i] appears before B[k] in S]),
             f(i, j-1) + sum(k=1 to i, [1 if B[j] appears before A[k] in S])
                       + sum(k=1 to j-1, [1 if B[j] appears before B[k] in S]))

Я использовал обозначение [1 if X] здесь для обозначения значения 1, если X истинно, и 0, если X ложно.

Матрица f может быть построена за время O(|A|^2 * |B|^2). Минимальная стоимость (количество инверсий относительно S) будет f(|A|, |B|).

Мы также можем реконструировать оптимальную перестановку, используя матрицу DP: мы строим ее сзади наперед. Мы начинаем с кортежа (i,j) = (|A|, |B|) и на каждом шаге в зависимости от того, какой из двух вариантов является минимальным в переходе DP, мы знаем, нужно ли нам ставить A[i] или B[j] в начало перестановки. Затем мы переходим к (i-1, j) или (i, j-1) в зависимости от того, что мы выбираем.

Вот реализация алгоритма, извините за отсутствие навыков работы с JS.

Одно определение, которое может быть разумным, состоит в том, чтобы свести к минимуму количество инверсий относительно порядка сервера при условии, что ограничения на общие столбцы двух порядков равны. Я не знаю навскидку алгоритма минимизации этой цели.

Это относится к ответу Николаса Б:

Теорема. Рассмотрим последовательность S = s₁, …, sₙ некоторого упорядоченного множества (например, целых чисел). Если i ‹ j и sᵢ > sⱼ, то замена sᵢ и sⱼ уменьшает количество инверсий, т. е. , пусть S' = s₁, …, sᵢ₋₁, sⱼ, sᵢ₊₁, …, sⱼ₋₁, sᵢ, sⱼ₊₁, …, sₙ; тогда S' имеет меньше инверсий, чем S.

Интуитивно сказано: если два элемента не в порядке и вы меняете их местами, вы ближе к отсортированному списку.

Доказательство. Обратите внимание, что единственными элементами, которые имеют различный относительный порядок в S и S', являются (sᵢ, sⱼ), (sᵢ, sₖ) и (sⱼ, sₖ) для каждый k, где i ‹ k ‹ j. Мы знаем, что (sᵢ, sⱼ) является инверсией в S, но не S', поэтому рассмотрим sₖ для некоторых таких k.

Либо sₖ ‹ sⱼ ‹ sᵢ, либо sⱼ ‹ sₖ ‹ sᵢ, либо sⱼ ‹ sᵢ ‹ sₖ (мы предполагаем, что элементы S< /em> быть уникальным).