Как найти расхождения в сортировке массивов?

Question

[Alex]

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

Comments

[riot26]

> сложный функционал под Joomla
> не может сравнить массивы

[Alex]

riot26, Не хочет изобретать велосипед, устроит? )

[Stalker_RED]

Александр, содержимое одинаковое, и нужно оценить только перестановки?

[Alex]

Stalker_RED, да, именно так

Answer 1

[Stalker_RED]

Если содержимое массивов одинаковое, и отличается только перестановками, то можно применить алгоритм Вагнера-Фишера, или Хишберга если всем операциям кроме транспозиции цену задрать.

Comments

[Alex]

Спасибо за направление поисков. Думаю, что в качестве метрики мне подойдет дистанция Дамерау-Левенштейна.

Answer 2

[Руслан .]

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

Answer 3

[Владимир Олохтонов]

Число транспозиций должно подойти.

Answer 4

[⚡ Kotobotov ⚡]

первыйМассив.зип(второйМассив).мап(абс(первыйЭлемент-второйЭлемент)).сумм
П. С.
если не понятно - то это сумма разностей элементов, по модулю.
если элементы не числа, то вам самостоятельно нужно придумать метрику для сравнения элементов.

Comments

[Alex]

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

Answer 5

[Дима]

Возможно, старый вопрос вам поможет. Там что то интересное про оценку периодических функций через ряды Фурье Как правильно сравнить массивы и оценить их схожесть?

Comments

[Alex]

Спасибо, почитаю