算法简介的问题7-6询问以下内容：
考虑一个我们不完全知道数字的排序问题。相反，对于每个数字，我们知道它所属的实线上的间隔。也就是说，给出n个形式为[a_i，b_i]的闭合区间，其中a_i <= b_i。我们希望对这些间隔进行模糊排序。 （Cormen，Leiserson，Rivest，＆Stein，2009，p.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 Ebook Central版]。来自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
正如@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 Ebook Central版]。来自https://ebookcentral.proquest.com
Lanman，D。R.（2006年3月13日）。 CS 157：作业3 [班级讲义]。来自http://alumni.media.mit.edu/~dlanman/courses/cs157/HW3.pdf
由于间隔不相互包含，您可以按左边缘，中间边缘或右边缘排序，您将得到相同的确切答案。
如果要使排序模糊，可以对间隔进行采样（假设您需要均匀或任何分布，并对采样值进行排序。