Хитрый алгоритм сортировки символов в массиве с сохранением отношений по порядку

Question

проблема

У меня есть несколько групп, которые определяют отношения символов .. например:

[A B C]

[A D E]

[X Y Z]

Что означают эти группы, так это то, что (для первой группы) символы A, B и C связаны друг с другом. (Вторая группа) Символы A, D, E связаны друг с другом ... и т. Д.

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

[B C A D E X Y Z]

или

[X Y Z D E A B C]

В этом результирующем массиве, поскольку символ A имеет несколько связей (а именно с B и C в одной группе и с D и E в другой), он теперь расположен между этими символами, что несколько сохраняет связь.

Обратите внимание, что порядок не важен. В результате X Y Z может быть помещен первым или последним, поскольку эти символы не связаны с какими-либо другими символами. Тем не менее, важна близость соответствующих символов.

Что мне нужно помочь в

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

Дальнейший пример

Чтобы дополнительно проиллюстрировать хитрость моей дилеммы, ЕСЛИ вы добавите другую группу отношений в приведенный выше пример Допустим,

[C Z]

Результат теперь должен выглядеть примерно так:

[X Y Z C B A D E]

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

Answer 1

Первое, что вам нужно сделать, это точно определить желаемый результат.

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

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

В любом случае должно быть легко найти хорошее приближение стандартными методами.

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

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

Answer 2

Проблема, как описано, по сути является проблемой рисования графика в одном измерении.

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

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

Существует множество алгоритмов для рисования графиков.В этом случае я бы пошел с порядком Фидлера , который упорядочивает вершины, используя определенный собственный вектор (вектор Фидлера) графа Лапласа графа .Упорядочение Фидлера является простым, эффективным и оптимальным в четко определенном математическом смысле.

Answer 3

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

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

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

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

Редактировать: Очевидно, как часть алгоритма, дублирование рва (тривиально).

Answer 4

Звучит так, будто вы хотите выполнить топологическую сортировку: http://en.wikipedia.org/wiki/Topological_sorting

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