Как вычислить абсолютное минимальное количество изменений для преобразования одного порядка сортировки в другого?

Если вы действительно пытаетесь свести к минимуму каждый бит данных, передаваемых по сети, как вы передаете свои данные? Например, вы как-то сжимаете? Использование 32-битного числа для порядка сортировки, вероятно, излишне, если у вас всего несколько тысяч элементов. 16 бит дают вам 65000 предметов за половину $ $ $. То же самое и с уникальными идентификаторами.

Предполагая, что:

• Вы можете хранить копии исходных и конечных данных как на ваших полевых устройствах, так и в базовой системе
• Когда вы говорите о свопах, вы имеете в виду два элемента в списки меняются местами друг с другом.

Лучшее решение, вероятно, следующее:

Вместо того, чтобы хранить список всех обменов, которые вы делаете по мере их выполнения, сравните свои начальные и конечные данные в конце дня, а затем сгенерируйте свопы, которые вам понадобятся для этого изменения. Это приведет к игнорированию любых мест в списке, которые остались неизменными, даже если они остались неизменными только потому, что серия перестановок «отменила» некоторые изменения. Если у вас есть данные в виде a, b, a, b, ... где a сообщает вам индекс следующих элементов, которые нужно оставить в том же порядке, в котором они находятся, а b сообщает вам индекс элемента, с которым нужно его поменять.

Поскольку вы выполняете только свопы, а не сдвиги, вы очень редко будете получать данные, подобные вашим образцам данных, где 30, 40 , и 50 находятся в том же порядке, но в немного другом месте. Поскольку количество обменов будет составлять от 1/4 до 1/10 количества исходных элементов в списке, у вас обычно будет большой кусок ваших данных в том же порядке и в том же месте, в котором он был изначально. Предположим, были произведены следующие свопы:

1 <-> 9
4 <-> 2
5 <-> 2 

Итоговым списком будет:

 1. 90                   
 2. 50                  
 3. 30                      
 4. 20                       
 5. 40                      
 6. 60                       
 7. 70                       
 8. 80                       
 9. 10                        

Таким образом, данные изменения могут быть представлены как:

 1,9,2,4,4,5

Это всего шесть значений, которые могут быть представлены как 16-битные числа (при условии, что вы выиграли в вашем первоначальном списке не более 16 000 пунктов). Таким образом, каждый «эффективный» своп может быть представлен одним 32-битным числом.

Я не уверен, что анализ свопов что-нибудь вам даст; как вы говорите, они могут отменять друг друга и приводить к запутанным результатам.

Я считаю, что ваш лучший вариант - определить в переупорядоченном списке те сегменты этого списка, которые не переупорядочены по сравнению с исходным список, даже если они начинаются в новом месте. В вашем примере это сегмент от 30 до 60. Таким образом, в своего рода кодировке длин серий, я бы отправил обратно карту сегментов, которая описывает местоположения и длины.

Опять же, используя данные вашего примера: список упорядоченного начала index, length:

{(9, 1), (3, 4), (1, 1), (8, 1), (7, 1), (2, 1)}

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

(Edit) На самом деле мне приходит в голову, что будут некоторые наборы данных, в которых список подкачки будет короче, если количество свопов невелико. Но, вероятно, будет некоторая точка переключения, в которой кодирование длин серий будет лучше; в этом случае я бы посоветовал вычислить оба и выбрать меньшее.

Вам нужна перестановка, необходимая для сортировки списка. Вы можете получить это, построив список индексов от 0 до n, а затем отсортировав этот список с помощью специальной функции сравнения, которая сравнивает элементы по соответствующим индексам. Например, в Python:

perm = sorted(range(len(l)), key=lambda x:l[x])

Затем вы можете отправить 'perm' по соединению и использовать его для получения отсортированного списка:

for x in perm:
  print perm[x]

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

Быстрое исправление может заключаться в использовании хэша Zobrist для выявления случаев, когда вы возвращаетесь к предыдущему порядку. То есть после каждого свопа вычисляйте хеш на основе достигнутой перестановки. Каждый хэш отображается в кратчайшую последовательность обменов, найденных до сих пор для этой конкретной перестановки.

Это можно легко расширить с помощью небольшого исследовательского поиска - хеш Zobrist был изобретен как способ оптимизации поиска в дереве игр.

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

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

Может быть полезно сначала использовать дельта-кодирование . Именно здесь вы храните различия между целыми числами, а не сами целые числа - это означает, что они лучше сжимаются с переменным байтом. Конечно, сохраняемые целые числа (возможно, идентификаторы изменяемых элементов в вашем случае) должны быть сначала отсортированы, но это не так.

Другое возможное решение, игнорирование структуры данных ...

Отправить набор идентификаторов / индексов для элементов, которые изменились (если это полностью случайное разреженное подмножество, просто перечислите их) и номер перестановки, описывающий изменение порядка этого подмножества. Для числа перестановок потребуется большое целочисленное представление - размер должен быть пропорционален log (n!), Где n - количество измененных элементов.

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

То есть ...

while not empty(indexes)
  item-to-swap := permutation-no remainder len(indexes)
  permutation-no := permutation-no div len(indexes)
  if item-to-swap != 0 : swap slot[indexes[0]], slot[indexes[item-to-swap]]
  indexes := tail(indexes)

The! = 0 требуется проверка, даже если все элементы необходимо изменить вначале - элемент мог быть переставлен вверх в правильное место ранее в цикле.

Это не пытается оптимизировать количество перестановок - элемент может быть несколько раз переставляли вверх, а затем переставляли вниз в правильное место. Тем не менее, число перестановок, вероятно, является оптимальным пространственным представлением для случайной перестановки массива. Учитывая, что ваша перестановка влияет только на небольшое подмножество полного массива, использование меньшего номера перестановки для этого подмножества имеет большой смысл.

правильное расположение. Тем не менее, число перестановки, вероятно, является оптимальным пространственным представлением для случайной перестановки массива. Учитывая, что ваша перестановка влияет только на небольшое подмножество полного массива, использование меньшего номера перестановки для этого подмножества имеет большой смысл.

правильное расположение. Тем не менее, число перестановки, вероятно, является оптимальным пространственным представлением для случайной перестановки массива. Учитывая, что ваша перестановка влияет только на небольшое подмножество полного массива, использование меньшего числа перестановки для этого подмножества имеет большой смысл.

Algo part:

A reordering of a list is called permutation. Each permutation can be split into a set of loops, with each loop of N elements requiring (N - 1) swaps. For example

1, 2, 3, 4, 5, 6 --> 3, 2, 4, 1, 6, 5

This can be split into 1 - 4 - 3 (requires 2 swaps) 2 - 2 (0 swaps) 5 - 6 (1 swap)

To find a solution you can just pick any element at a wrong position and put it on its place.

Details part:

Of course, you can use smaller data types, RLE or some other encoding algorithms and so on.

Very theoretical but non-practical part.

All permutations of a sequence of N numbers can be lexicographically ordered, and one number from 0 to (N! - 1) is enough to represent the sequence. So, theoretically best answer is: compute the index of the permutation, transfer it, recreate the permutation by that index.