用快速排序法对区间进行模糊排序

Question

算法介绍中的问题7-6要求如下：

考虑一个排序问题，其中我们不知道确切的数字。相反，对于每个数，我们知道它所属的真实线上的一个区间。即，给出了形式a_i，b_i，a_i <= b_i的n个闭区间，并给出了模糊排序的n个闭区间。(Cormen，Leiserson，Rivest，& Stein，2009年，第189页)

Demaine和Goldwasser (2004年)澄清了“没有间隔包含任何其他间隔”，或者"if 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.，Ri背心，R.L.，& Stein，C. (2009)。算法导论(第三版)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日)。政务司司长157:作业3班讲义。从http://alumni.media.mit.edu/~dlanman/courses/cs157/HW3.pdf检索

Answer 1

正如@tobias_k所指出的，我的问题是不理解这个问题，也不理解一个正确的解决方案。关于正确的解决办法，Cormen等人。(2009)指出，“我们希望对这些区间进行模糊排序，即产生一个区间的排列，使得对于j= 1，2，.，n，存在着c_j∈a_i_j，b_i_j stated c_1 <= 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.，Ri背心，R.L.，& Stein，C. (2009)。算法导论(第三版)ProQuest电子书中央版。从https://ebookcentral.proquest.com检索

Lanman，D.R. (2006，3月13日)。政务司司长157:作业3班讲义。从http://alumni.media.mit.edu/~dlanman/courses/cs157/HW3.pdf检索

Answer 2

由于间隔不包含彼此，您可以按左边、中边或右边进行排序，您将得到相同的精确答案。

如果要使排序变得模糊，可以对间隔进行抽样(假设是一致的或任意分布的)，并对抽样值进行排序。

Answer 3

我知道这是个老问题，但这是我的解决办法。它也是用C写的，但它应该能很好地传达思想。

// struct representing an interval
typedef struct interval interval;
struct interval{
    double first;
    double second;
};

// fuzzy-sort the interval [start, end)
void fuzzy_sort(size_t start, size_t end, interval arr[])
{
    size_t x = start;       // head of the < partition + 1
    size_t y = start + 1;   // head of the = partition + 1
    size_t z = end;         // bottom of the > partition

    if(y >= z)
        return;
    // common overlap interval of equal
    // elements starting
    // with arr[start] as pivot
    double p1 = arr[start].first, p2 = arr[start].second;

    while(y < z){
        if(arr[y].second < p1){
            interval hold = arr[y];
            arr[y] = arr[x];
            arr[x] = hold;
            ++x, ++y;
        }
        else if(arr[y].first > p2){
            interval hold = arr[y];
            arr[y ] = arr[z - 1];
            arr[z - 1] = hold;
            --z;
        }
        else{
            // max
            p1 = p1 < arr[y].first ? arr[y].first : p1;
            // min
            p2 = p2 > arr[y].second ? arr[y].second : p2;
            ++y;
        }
    }
    fuzzy_sort(start, x, arr);
    fuzzy_sort(z, end, arr);
}

// return 1 if arr is fuzzy-sorted, else 0
int is_fuzzy_sorted(size_t n, interval arr[])
{
    double last = arr[0].first;
    for(int i = 1; i < n; ++i){
        if(last > arr[i].second)
            return 0;
        last = last < arr[i].first ? arr[i].first : last;
    }
    return 1;
        
}

在执行过程中，数组看起来可能如下所示

-less-->|-equals-->|<----unpartitioned---->|<---greater--

其思想是将数组划分为三个区域:与枢轴具有相互重叠间隔的区域、完全小于此区间的区域和完全大于此区间的区域。具有相互重叠间隔(中间分区)的分区可能以任意顺序出现，因此该算法只对左右分区进行递归排序。此外，如果有一个共同的间隔，该算法将精确地穿过数组，正如Cormen等人中的原始问题所述。(2022)。

当输入运行时，代码输出：{(2，2)，(4，6)，(7，9)，(5，7)，(6，8)，(8，10)，(11，15)，(9，11)，(12，16)，(13，20)，(19，21)，(20，24)}，这也是一个正确的答案。

我只是在今天早上才开发了它，并且粗略地解释了它的工作原理，但没有精确的数学解释。请随便批评。