2015-07-17 3 views
-1

С учетом входных данных в виде множества сравнений, таких как «а> Ь», «d < B», «C> а», ...Сортировка данных по набору сравнений

Как я могу построить сортированный (от максимального к наименьшему) порядок? (Мне не нужно беспокоиться о том, что вам дадут невозможные входы, всегда будет ровно один правильный порядок.)

Я думал о написании функции как параметра для std :: sort, которая будет искать каждый элемент в список сравнений, но я не думаю, что это будет связано с идеей транзитивности.

+0

Знаете ли вы заранее все значения потенциальных элементов? –

+0

@EdHeal Извините, если мне показалось, что я прошу ввести код. Просто ищите направление для входа или алгоритм для изучения. – gautam

+0

@ Mr.Llama Я не ... Я должен был бы получить это из входных сравнений. – gautam

ответ

2

На самом деле вам не нужно выполнять сортировку на основе сравнения.

Постройте орграф с направленным фронтом для каждого неравенства и запустите Topological Sorting. Это будет работать в линейном времени.

Библиотека графа ускорения имеет этот implemented.

Смежные вопросы