Нечеткие интервалы сортировки с вторичным критерием сортировки - PullRequest
Новая
       19

Нечеткие интервалы сортировки с вторичным критерием сортировки

0 голосов
/ 11 мая 2019

Я хочу отсортировать список предметов по двум критериям. Каждый элемент содержит интервал и число. 

Items[0] = {Interval=[10..30], Number = 7}
Items[1] = {Interval=[20..40], Number = 5}
Items[2] = {Interval=[30..50], Number = 3}
Items[3] = {Interval=[40..60], Number = 2}

Я хочу «нечеткую сортировку» этого списка по интервалам: порядок, в котором ни одна нижняя граница интервала не превышает верхнюю границу более позднего элемента.

Например, items[3] не следует сортировать до items[0], поскольку [40..60] строго больше, чем [10..30]. Но items[1] может произойти до или после items[0], потому что их интервалы перекрываются.

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

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

Таким образом, следующий порядок будет действительным, отсортированным по Interval по возрастанию, затем по Number по возрастанию: 

Items[2] = {Interval=[30..50], Number = 3}
Items[1] = {Interval=[20..40], Number = 5}
Items[0] = {Interval=[10..30], Number = 7}
Items[3] = {Interval=[40..60], Number = 2}

Существует несколько одинаково действительных решений. Это также будет действительный заказ с использованием тех же критериев: 

Items[0] = {Interval=[10..30], Number = 7}
Items[3] = {Interval=[40..60], Number = 2}
Items[2] = {Interval=[30..50], Number = 3}
Items[1] = {Interval=[20..40], Number = 5}

Существует ли эффективный алгоритм для нахождения такого порядка, кроме грубой силы?

Есть имя для этого типа или сортировки?

1 Ответ

1 голос
/ 11 мая 2019

Создайте график, где каждая вершина является интервалом.

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

Может быть возможно избежать времени выполнения O (n²), которое мы получили бы, зацикливаясь на всех парах.Если мы отсортируем интервалы по времени окончания, итерация интервалов в этом порядке позволит нам быстро найти все интервалы, которые перекрываются с любым заданным интервалом (мы можем просто посмотреть самое последнее время окончания в этом списке, которое было до начала этого интервала).время).Затем нам нужно выяснить, как избежать создания ненужных ребер - для [1,2], [3,4] и [5,6] между [1,2] и [5 будет ненужный ребро], 6], потому что они связаны через [3,4].

Края представляют, какие интервалы должны предшествовать каким интервалам в нашем отсортированном списке.

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

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

Это будет O (n²), но, возможно, его можно оптимизировать до O (n log n).

Возьмите пример: 

Items[0] = {Interval=[10..30], Number = 7}
Items[1] = {Interval=[20..40], Number = 5}
Items[2] = {Interval=[30..50], Number = 3}
Items[3] = {Interval=[40..60], Number = 2}

Единственным ребром в графе будет [10, 30] → [40, 60].

Это означает, что мы можем выбрать любую вершину, кроме [40, 60].

Сначала мы выберем [30, 50], поскольку он имеет наименьшее число между оставшимися элементами (3 <5 и 3 <7). </p>

Затем мы выберем [20,40] с 5 <7. </p>

Затем мы выберем [10, 30] и уберем ребро в [40, 60], что позволит нам выбрать [40, 60].

Наконец мы выберем [40, 60].

...