合并n个列表并对数据进行排序，以保持原始顺序/约束 [英] Merge n lists and sort data maintaining original order/constraint

问题描述

我在编码比赛中遇到了以下问题。我尝试了很多，但是一个私人测试用例总是对我失败，给出错误的答案，并且我无法弄清楚为什么我的下面的方法会失败。我没有天真的解决方案来生成压力测试用例并进行比较。此外，也不会发表社论。
因此，我正在寻找可能的人指出我的方法中的缺陷。

I encountered the below problem in a coding competition. I tried a lot but a private test case was always failing for me with wrong answer and I am unable to figure out why my below approach would fail. I've no naive solution to generate stress test cases and compare. Also, there will be no editorial published. So, I am looking for someone to point out the flaw in my approach if possible.

以下是对该问题以及我所采取的措施的详细说明

Following is a detailed description of the problem and what I've tried till now.

问题：
有多个区域，并且根据每个区域在各个区域中的排名为您提供分数。
例如：

Problem: There are multiple regions and you are given marks for students for each region as per their rank in the respective region. For example:

Region1:
StudentName, Score
A,           50.0
B,           60.0  
C,           40.0 

Region2:
StudentName, Score
D,           30.0
E,           10.0
F,           20.0 

在以上数据中，学生A在Region1中排名1，B在Region1中排名2，C在Rank3中排名在Region1中。
同样，D在Region2中具有Rank1，E具有Rank2，F具有Rank3。

In the above data, Student A has rank 1 in Region1, B has Rank2 in Region1 and C has Rank3 in Region1. Similarly, D has Rank1 in Region2, E has Rank2 and F has Rank3.

• 学生的分数可能更低，但仍然在同一地区的排名较高。例如，在Region1中A的排名优于B，即我们应该假设每个区域的数据已经按照排名进行了排序。

任务是合并所有区域的数据并创建根据得分排名的全局数据。约束条件是，该区域中排名较低的任何学生，其排名都不能比该区域中其他学生的排名要高出原始区域数据中的其他学生。

Our task is to merge all region's data and create a global data ranked according to score. The constraint is that any student who was at a lower rank in the region still cannot have a rank above the other students from it's region having a better rank than it in the original region data.

例如：

Region1:
A, 50.0
B, 60.0
C, 40.0 

Region2:
D, 30.0
E, 10.0
F, 20.0

将合并为：

A, 50.0
B, 60.0
C, 40.0 
D, 30.0
E, 10.0
F, 20.0

顺序没有根据分数变化，因为根据区域约束，B总是低于A，F总是低于E。

The order did not change according to score because B will always be lower than A and F will always be lower than E as per their region's constraints.

其他测试用例：

Region1:
A, 50.0
B, 60.0
C, 70.0 

Region2:
D, 30.0
E, 20.0
F, 10.0

再次按照A，B，C，D，E，F的顺序排列结果

again results in the order of A,B,C,D,E,F

Region1:
A, 60.0
B, 80.0
C, 100.0 

Region2:
D, 70.0
E, 90.0
F, 110.0

将导致：
D，E，F，A，B，C

will result in: D, E, F, A, B, C

但是，

Region1:
A, 11.5
B, 8.5
C, 10.0 

Region2:
D, 12.0
E, 9.0
F, 9.5

将导致：

D, 12.0
A, 11.5
E, 9.0 
B, 8.5
C, 10.0
F, 9.5

Constraints:
1<=number of regions<=6
score can be upto 7 decimal places

我的方法是将所有输入数据添加到一个列表中并保持稳定的排序，即如果两个学生的区域相同，则比较他们在区域中的排名，否则比较分数。

My approach is to add all the input data to one list and maintain a stable sort i.e. if the zone is same for two students, compare their rank in the zone, otherwise compare scores.

static class Student implements Comparable<Student>
{
String name;
double score;
int zone;
int rank;

//constructor

public int compareTo(Student o)
{
if(this.zone == o.zone)
{
//lower i.e. better rank
return Integer.compare(this.rank, o.rank);
}
//higher i.e. better score
return Double.compare(o.score, this.score);
}

}

main()
{
//read data from console input into an ArrayList<Student> students
Collections.sort(students);
//print each student from students

}

问题没有提到在不同地区的两个学生的分数是否相等。在这种情况下，我尝试使用各自在区域中的等级打破平局，但私人测试用例仍然失败。我最初以为该问题可能缺少一些信息，但是我在比赛仪表板中看到许多成功提交该问题的信息。这就是我认为我缺少某些东西的原因，问题并不像我想的那么简单。但是，我无法提出一个测试案例来验证这一假设。

The question does not mention if score could be equal for two students in different zones. I've tried breaking the tie in that case using their respective ranks in the zone but the private test cases keep failing. I initially thought that the question might have some missing information but I see many successful submissions for this question in the competition dashboard. This is the reason I believe I am missing something and the question is not as simple as I am thinking. But, I've not been able to come up with a test case to validate this assumption.

谢谢！

推荐答案

据我所知，要求是根据分数对学生进行排序，但是还存在一个额外的约束条件，即必须保留区域内学生的相对排序。

As I understand the question, the requirements are to sort the students according to score, but with the additional constraint that the relative ordering of students within a region be preserved.

给出问题中列出的示例之一的输入数据，

Given the input data from one of the examples listed in the question,

Region1:
A, 11.5
B, 8.5
C, 10.0 

Region2:
D, 12.0
E, 9.0
F, 9.5

仅按分数排序将得到以下结果：DACFEB。

sorting only by score gives the following result: DACFEB.

但是，要保留一个区域内的相对顺序，则需要以下部分排序 A< B ＜ C和D ＜ E ＜ F。

However, the constraint about preserving relative ordering within a region requires the following partial orderings A < B < C and D < E < F.

OP将这个特定的示例作为DAEBCF给出了解决方案。在对该问题的评论中，我为该示例提出了另外两种可能的解决方案：DABCEF和DAEFBC。我看不到任何标准可以让我们决定哪些可行的解决方案是正确的。这样，问题就受到限制。一个人可以争论哪种解决方案比其他解决方案更可取，但是这样做会引入新的约束条件，而这些约束条件在原始问题中并未得到证实。

The OP gives the solution to this particular example as DAEBCF. In comments on the question, I suggested two other possible solutions for this example: DABCEF and DAEFBC. I don't see any criteria which let us decide which of these possible solutions is the correct one. As such, the problem is underconstrained. One can argue about which of these solutions is preferable to the others, but doing so will introduce new constraints which aren't in evidence in the original question.

鉴于是满足问题中所有条件的多种解决方案，这意味着该域中没有总排序。此外，鉴于正确的比较器必须对其域的值强加全部排序，因此无法为该域编写适当的比较器。

Given that there are multiple solutions that meet all the criteria in the problem, it means that there is no total ordering of values in this domain. Further, given that a correct Comparator must impose a total ordering on the values of its domain, it follows that it is not possible to write a proper Comparator for this domain.

当然，可以编写具有某些行为的正确Comparator，并且会比其他方法更喜欢其中一种。这样做将隐式地实现不是问题陈述一部分的其他约束。实际上，似乎 Vincent van der Weele 已经这样做了。语句下一个空白点必须由一个区域中排名最高的剩余元素填充。哪个？得分最高的那个引入了附加约束。这将导致OPEB建议订购DAEBCF。尽管这是明智的做法，但这必然是正确的排序。

Of course, it's possible to write a correct Comparator that has some behavior, and that will prefer one of these possible solutions over the others. Doing so will implicitly be implementing additional constraints that aren't part of the problem statement. In fact, it appears that Vincent van der Weele has done so. The statement "The next empty spot must be filled by the highest ranked remaining element of one of the regions. Which one? The one with the highest score" introduces the additional constraint. It results in the ordering DAEBCF, which was suggested by the OP. While this is sensible, but it's necessarily the "right" ordering.

另一种算法可能如下。 1）从一个空的结果列表开始，并按排名顺序维护每个地区的学生列表。 2）查找得分最高的其余学生。 3）将该学生和同一地区的高等学生带入结果中，并保持相对顺序。 4）重复直到没有学生。

An alternative algorithm might be as follows. 1) Start with an empty result list and maintain lists of students from each region in rank order. 2) Find the remaining student with the highest score. 3) Take that student, and higher-ranked students within the same region, and append them to the result, preserving relative order. 4) Repeat until no students remain.

将此算法应用于DABCEF中的示例输入结果。这是明智的，但是以不同的方式。再次，我们不知道这是否是正确的答案。

Applying this algorithm to the example input results in DABCEF. This is sensible, but in a different way. Again, we don't know whether it's the "right" answer.

要么编程竞赛中的问题最初没有指定好，要么丢失了一些信息在比赛的问题陈述和OP的此处在Stack Overflow上的问题之间。

Either the problem in the programming competition was ill-specified to begin with, or some information was lost between the competition's problem statement and the OP's question here on Stack Overflow.

这篇关于合并n个列表并对数据进行排序，以保持原始顺序/约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！