区间的模糊排序 [英] Fuzzy Sorting of Intervals

问题描述

这是关于以下问题的解决方案间隔的模糊排序来自书算法简介

我有在互联网上找到了一些解决方案。但有疑问。

在所有给定的解决方案中，我们只将左分区分为左和中，以便中与枢轴元素重叠，无需排序。 br />
为什么我们不将右分为中和右，以便中与枢轴重叠，无需排序。



问题

考虑一个排序问题，其中的数字不确切。相反，对于每个数字，我们知道它所属的实线上的间隔。也就是说，我们给出n个形式为[ai，bi]的闭区间，其中ai≤bi。目标是对这些间隔进行模糊排序，即在间隔中产生排列


互联网上的解决方案

courses.csail.mit.edu/6.046/spring04/handouts/ps2-sol.pdf

< a href =http://web.media.mit.edu/~dlanman/courses/cs157/HW3.pdf> web.media.mit.edu/~dlanman/courses/cs157/HW3.pdf





主持人须知

如果此问题不明确我道歉。我不想臃肿这篇文章。因此，我只在帖子末尾给出了实际解决方案的链接。我希望熟悉这个问题的人能够在不进入实际解决方案的情况下认识到这个问题。至于我的目标，只是解决这个问题，因为我正在研究我的算法。



修复了解决方案链接中的URL。[ / edit]

This is regarding the solution of the following problem "Fuzzy Sorting of Intervals" from the book "Introduction to Algorithm"
I have found a few solutions on the internet. But have a doubt.
In all the given solutions, we are only splitting the Left partition into "Left" and "Middle" so that "Middle" overlaps with pivot element and need not be sorted.
Why do we not also split the "Right" into "Middle" and "Right" so that "Middle" overlaps with pivot and need not be sorted.

Problem
Consider a sorting problem in which the numbers are not known exactly. Instead, for each number, we know an interval on the real line to which it belongs. That is, we are given n closed intervals of the form [ai, bi], where ai ≤ bi. The goal is to fuzzy-sort these intervals, i.e., produce a permutation 〈i1, i2,..., in〉 of the intervals such that there exist cj in each [aj,bj] , satisfying c1 ≤ c2 ≤ ··· ≤ cn.

Solutions on the internet
courses.csail.mit.edu/6.046/spring04/handouts/ps2-sol.pdf
web.media.mit.edu/~dlanman/courses/cs157/HW3.pdf


Note to Moderator
I apologize if this question is not clear. I did not want to bloat this post. Hence I only gave the links to the actual solution at the end of the post. I was hoping people familiar with the problem will recognize it without going into the actual solution. As for my goal, it is simply to solve this problem as I am brushing up on my Algorithms.

[edit - Peter_in_2780] fixed URLs in links to solutions.[/edit]

推荐答案

我只阅读你链接的第一个解决方案，但我猜测另一个使用相同的数学家的速记。如果仔细阅读，他们会将左侧分区递归，并暗示在右侧完成相同的过程。 （事实上​​，再次阅读它们，它们实际上至少在两个地方明确说明了。）



所以基本上，他们正在使用左分区作为示例他们有一个名字可以用来描述递归步骤。

如果我站在黑板前解释它，我可以指出并说这一个，但这有点难以写在纸上。



干杯，

彼得



ps我编辑了你的问题以修复链接。

I only read the first solution you linked to, but I'm guessing the other one uses the same mathematicians' shorthand. If you read it carefully, they take the left partition to recurse on, and imply that the same process is done on the right. (In fact, reading it again, they actually state that explicitly in at least two places.)

So basically, they are using the left partition AS THE EXAMPLE just so they have a name to use as they describe the recursive step.
If I was standing in front of a blackboard explaining it, I could just point and say "this one", but that's a bit hard to do in a paper.

Cheers,
Peter

p.s. I edited your question to fix the links.

因为在书中的原始分区算法中，对于左分区中的每个元素k，k< = x;而对于右分区中的每个元素k，k> 1。 x。



这就是为什么左分区可以进一步分区为LEFT和MIDDLE的原因。顺便说一句，这种改进与间隔排序无关。它也可以应用于普通的快速排序，只是它不太可能拥有与区间排序一样多的相等元素，其中交集实际上意味着相等。

Because in the original partition algorithm in the book, for each element k in the left partition, k <= x; While for each element k in the right partition, k > x.

That's why the left partition can be further partitioned to LEFT and MIDDLE. By the way, this improvement has nothing to do w/ interval sorting. It can be applied to normal quicksort as well, just that it's less likely to have as many equal elements as in interval sorting where intersection really means equality.

这篇关于区间的模糊排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！