Как я могу отсортировать эту «матрицу» данных?

Question

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

Смотрите этот пример набора данных:

Слева является сырым "несортированный" вид. Справа - правильно отсортированный (на мой взгляд) список.

Каждый квадрат показывает количество раз, когда они соревновались друг с другом, и процент побед. Они затенены на основе процента.

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

Я просто не совсем уверен в наилучшем способе автоматизации этого.

Цифры в конце каждой строки - это краткая идея, которую я собрал и равную сумме в строке (число столбцов в процентах 50 *). Как вы можете видеть, они выполняют довольно хорошую работу, причем только первые две строки являются «неправильными». Тем не менее, они не придают никакого значения количеству встреч, но только процент выигрыша.

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

Я ожидаю, что смогу срубить что-нибудь вместе, чтобы сделать эту работу ... но я чувствую, что у SO будет около . лучшие идеи, и я все уши.

Answer 1

A tournament - график, в котором существует ровно одно направленное ребро между каждой парой вершин; чтобы создать такой график из вашего ввода, вы можете сделать граф с вершиной для каждого игрока, а затем «указать» каждое из краев между двумя игроками в направлении игрока, выигравшего большинство игр (вам нужно будет разорвать галстуки как-то).

Если вы сделаете это, и если нет циклов A> B> ...> А типа я упомянул в моем комментарии в этом графике, то граф является транзитивным , и вы можете заказать игроки используют график topological sort. Это занимает только линейное время в числе ребер, т. Е. O (n^2) для n игроков.

Если таких циклов, то нет «идеального» заказа игроков: любой заказ будет размещать по крайней мере одного игрока после того, как какой-либо игрок избит. В этом случае разумной альтернативой является поиск заказов, которые минимизируют количество этих «нарушений границ». Это, оказывается, хорошо изученная NP-трудная проблема в информатике (минимальная) Arc Arc Arc в турнирах (FAST). A feedback arc set представляет собой набор направленных ребер («дуги»), которые, если они удалены из графика, оставят график без целых циклов, который затем можно легко превратить в порядок с использованием топологической сортировки, как и раньше.

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

Answer 2

Просто чтобы добавить к ответу j_random, вы можете выделить циклы, используя что-то вроде Tarjan's strongly connected components algorithm. В рамках сильно связанного компонента вы можете использовать другой метод для сортировки элементов.