python-3.x - 使用快速排序对区间进行模糊排序

Question

Introduction to Algorithms 的问题 7-6 提出以下问题:

考虑一个我们不确切知道数字的排序问题。相反，对于每个数字，我们知道它所属的实线上的一个区间。也就是说，我们给出了 n 个形式为 [a_i, b_i] 的闭区间，其中 a_i <= b_i。我们希望对这些区间进行模糊排序。 (Cormen、Leiserson、Rivest 和 Stein，2009 年，第 189 页)

Demaine 和 Goldwasser (2004) 阐明“没有区间包含任何其他区间”或“如果 a_i <= a_j，则 b_i，b_j。”

我已经实现了 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 数组并从那里进行调整，但没有帮助。我得到了相同的结果。

引用资料:

Cormen, T. H.、Leiserson, C. E.、Rivest, R. L. 和 Stein, C. (2009)。 算法简介(第 3 版)[ProQuest 电子书中央版]。检索自 https://ebookcentral.proquest.com

Demaine, E. 和 Goldwasser, S.(2004 年，2 月 24 日)。问题集 2 [类讲义]。检索自 https://courses.csail.mit.edu/6.046/spring04/handouts/ps2-sol.pdf

Lanman, D. R.(2006 年，3 月 13 日)。 CS 157:作业 3 [类讲义]。检索自 http://alumni.media.mit.edu/~dlanman/courses/cs157/HW3.pdf

Answer 1

正如@tobias_k 所指出的，我的问题是不理解问题或正确的解决方案是什么样的。关于正确的解决方案，Cormen 等人。 (2009) 指出，“我们希望对这些区间进行模糊排序，即产生区间排列，使得对于 j = 1, 2, ..., n，存在满足 c_1 的 c_j ∈ [a_i_j, b_i_j] <= c_2 <= ... <= c_n。”

因此，对于输入 [(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)]，是一个正确的解决方案。

你看，就像 Cormen 等人一样。 (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 年)的第四页，并在解决问题之前真正了解什么是正确的模糊排序。

引用资料:

Cormen, T. H.、Leiserson, C. E.、Rivest, R. L. 和 Stein, C. (2009)。 算法简介(第 3 版)[ProQuest 电子书中央版]。检索自 https://ebookcentral.proquest.com

Lanman, D. R.(2006 年，3 月 13 日)。 CS 157:作业 3 [类讲义]。检索自 http://alumni.media.mit.edu/~dlanman/courses/cs157/HW3.pdf