Нечеткая сортировка интервалов с помощью быстрой сортировки

Question

Задача 7-6 из Введение в алгоритмы задает следующее:

Рассмотрим задачу сортировки, в которой мы не знаем точно числа.Вместо этого для каждого числа мы знаем интервал на реальной линии, к которой он принадлежит.То есть нам даны n закрытые интервалы вида [ a_i , b_i ], где a_i <= b_i.Мы желаем <strong> нечеткой сортировки этих интервалов.(Cormen, Leiserson, Rivest, & Stein, 2009, p. 189)

Демейн и Голдвассер (2004) уточняют, что «ни один интервал не содержит никакого другого интервала» или что «если a_i <= a_j, то b_i, b_j. "</p>

Я реализовал псевдокод от Lanman (2006).Хотя я думаю, что я очень близок, функции не возвращают правильный результат на моем тестовом вводе.Мой код выглядит следующим образом:

def sort_fuzzy(intervals, p, s):
    """
    Given a list whose elements are 2-tuples that represent inclusive intervals,
    sort it in place by partitioning it.  Assume no interval completely contains
    any other interval.
    :param  list intervals: An unsorted list of 2-tuples that represent a \
                            closed interval in which a fuzzy value lies.
    :param  int p:          Starting index of the region to sort.
    :param  int s:          Ending index of the region to sort.
    """

    if p < s:
        x = find_intersection(intervals, p, s)
        r = partition_fuzzy_right(intervals, p, s, x)
        q = partition_fuzzy_left_middle(intervals, p, r, x)
        sort_fuzzy(intervals, p, q - 1)
        sort_fuzzy(intervals, r + 1, s)

def partition_fuzzy_right(intervals, p, s, x):
    """
    Given a list whose elements are 2-tuples that represent inclusive intervals,
    partition it into three regions: p to r - 1, r, and r + 1 to s.
    :param  list intervals: An unsorted list of 2-tuples that represent a \
                            closed interval in which a fuzzy value lies.
    :param  int p:          Starting index of the region to sort.
    :param  int s:          Ending index of the region to sort.
    :param  tuple x:        Intersection of intervals.
    """

    i = p - 1
    for j in range(p, s):
        if intervals[j][0] <= x[0]:
            i += 1
            intervals[i], intervals[j] = intervals[j], intervals[i]

    intervals[i + 1], intervals[s] = intervals[s], intervals[i + 1]

    return i + 1

def partition_fuzzy_left_middle(intervals, p, r, x):
    """
    Given a list whose elements are 2-tuples that represent inclusive intervals,
    partition it into four regions: p to q - 1. q, q + 1 to r, and r + 1 to s.
    :param  list intervals: An unsorted list of 2-tuples that represent a \
                            closed interval in which a fuzzy value lies.
    :param  int p:          Starting index of the region to sort.
    :param  int s:          Ending index of the region to sort.
    :param  tuple x:        Intersection of intervals.
    """

    i = p - 1
    for j in range(p, r):
        if intervals[j][1] < x[1]:
            i += 1
            intervals[i], intervals[j] = intervals[j], intervals[i]

    intervals[i + 1], intervals[r] = intervals[r], intervals[i + 1]

    return i + 1

def find_intersection(intervals, p, s):
    """
    Given a list whose elements are 2-tuples that represent inclusive intervals,
    return the intersection of a pivot interval and the 2-tuples if one exists.
    Otherwise, just return the pivot interval.
    :param  list intervals: An unsorted list of 2-tuples that represent a \
                            closed interval in which a fuzzy value lies.
    :param  int p:          Starting index of the region to sort.
    :param  int s:          Ending index of the region to sort.
    """

    x = intervals[s]

    for i in range(p, s):
        if intervals[i][0] <= x[1] and intervals[i][1] >= x[0]:
            if intervals[i][0] > x[0]:
                x = (intervals[i][0], x[1])
            if intervals[i][1] < x[1]:
                x = (x[0], intervals[i][1])

    return x

if __name__ == '__main__':
    list = [(13, 20), (19, 21), (9, 11), (5, 7), (12, 16), (8, 10), (7, 9), (4, 6), (20, 24), (2, 2), (6, 8), (11, 15)]
    print(list)
    sort_fuzzy(list, 0, len(list) - 1)
    print(list)

Буду очень признателен за любые подсказки и подсказки.Я работал над этим в течение нескольких дней.

ОБНОВЛЕНИЕ: более простая реализация псевдокода в Lanman (2006), то есть разбиение входного массива кортежей на массивы A и B и адаптация изтам не помогло.Я получил тот же результат.

Список литературы:

Кормен, Т. Х., Лейзерсон, К. Э., Ривест, Р. Л. и Штейн, С. (2009). Введение в алгоритмы (3-е изд.) [ProQuest Ebook Central версия].Получено от https://ebookcentral.proquest.com

Demaine, E. & Goldwasser S. (2004, 24 февраля).Задача 2 [Класс раздаточного материала].Получено из https://courses.csail.mit.edu/6.046/spring04/handouts/ps2-sol.pdf

Lanman, DR (2006, 13 марта).CS 157: Задание 3 [раздаточный материал для класса].Получено с http://alumni.media.mit.edu/~dlanman/courses/cs157/HW3.pdf

Answer 1

Как указал @tobias_k, моя проблема не заключалась в том, чтобы понять вопрос или как выглядит правильное решение.Что касается правильного решения, Cormen et al.(2009) заявил: «Мы хотим нечеткой сортировки этих интервалов, т. Е. Произвести перестановку интервалов таким образом, чтобы для j = 1, 2, ..., n существовал c_j ∈ [a_i_j, b_i_j], удовлетворяющий c_1<= c_2 <= ... <= c_n. "</p>

Итак, для ввода [(13, 20), (19, 21), (9, 11), (5, 7), (12, 16), (8, 10), (7, 9), (4, 6), (20, 24), (2, 2), (6, 8), (11, 15)] мой код выводит [(2, 2), (4, 6), (6, 8), (7, 9), (5, 7), (8, 10), (9, 11), (11, 15), (13, 20), (12, 16), (19, 21), (20, 24)], что равно aправильное решение.

Видите, как и Cormen et al.(2009) писал, что если любое число в интервале больше или равно любому числу в интервале, предшествующем ему, оно может правильно следовать за этим предыдущим интервалом.Другими словами, рассмотрим следующее:

2 | 2 ∈ [2, 2] <= 4 | 4 ∈ [4, 6] <= 6 | 6 ∈ [6, 8] <= 7 | 7 ∈ [7, 9] <= 7 | 7 ∈ [5, 7] 8 | 8 ∈ <= [8, 10] <= 9 | 9 ∈ [9, 11] <= 11 | 11 ∈ [11, 15] <= 13 | 13 ∈ [13, 20] <= 13 | 13 ∈ [12, 16] <= 19 | 19 ∈ [19, 21] <= 20 | 20 ∈ [20, 24]

не необходимо, чтобы левые ребра сортировались в порядке возрастания, а только чтобы интервалы перекрывались вкакой-то нечетко увеличивающийся порядок.Посмотрите четвертую страницу Lanman (2006) и действительно поймите, что такое правильная нечеткая сортировка, прежде чем решать проблему.

Список литературы:

Кормен, TH, Лейсон, CE, Rivest, RL, &Stein, C. (2009). Введение в алгоритмы (3-е изд.) [ProQuest Ebook Central версия].Получено из https://ebookcentral.proquest.com

Lanman, DR (2006, 13 марта).CS 157: Задание 3 [раздаточный материал для класса].Получено с http://alumni.media.mit.edu/~dlanman/courses/cs157/HW3.pdf

Answer 2

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

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