基于其值的自定义排序向量

Question

我有以下向量：

std::vector< std::pair<int, int> > vectorOfPairs

包括以下项目：

0, 1
0, 2
1, 4
2, 3
3, 4
4, 5
5, 6

我想以一种方式对它们进行排序，即每对中的第二个分量等于向量中最近对的第一个分量，如下所示：

0, 1
1, 4
4, 5
5, 6
0, 2
2, 3
3, 4

我不知道这是否足够明显，我会附上一张图片，显示我正在尝试做的事情：

我觉得我应该使用sort和某种比较器，但我迷失在这里：

std::sort(vectorOfPairs.begin(), vectorOfPairs.end(), MyComparator);

---

bool MyComparator(pair<int, int> a, pair<int, int> b) {
    if(some_kind_of_comparison){
        return true;
    } 
    return false;
}

我是c ++的新手，如果有人可以帮我解决如何做到这一点的伪代码，我将非常感激。

Answer 1

您可以将此问题视为图形问题。每个对都代表有向图中的边。例如，对（0,2）表示“从节点0到节点2有一条边”，而对（2,5）表示“从节点2到节点5有一条边”。

如果以这种方式考虑事物，每对的第二个元素与下一对的第一个元素匹配的一系列边对应于图中的路径。例如，您给出的排序顺序中有两个路径：0 - > 1 - > 4 - > 5 - > 6和0 - > 2 - > 3 - > 4.因此，您尝试的问题求解如下：如何将图中的边缘分成最小数量的边缘不相交路径？一旦你解决了这个问题，你就可以按照你想要的任何顺序输出这些路径。

你无法用std::sort解决这个问题。例如，假设您有边（0,1），（0,2），（2,3）和（1,3）。在这种情况下，这两个顺序都是有效的：

(0, 1)          (0, 2)
(1, 3)          (2, 3)
(0, 2)          (0, 1)
(2, 3)          (1, 3)

这是个问题。因为（0,1）在第一个排序中位于（0,2）之前，而（0,2）在第二个排序中位于（0,1）之前，所以比较器可能是严格弱排序的唯一方法是if（0,1） ）和（0,2）是无法比拟的。这意味着在任何排序的排序中，由于transitivity of incomparability，（0,1）和（0,2）（包括）之间的所有元素也必须是无与伦比的。换句话说，我们应该能够采取任何排序，置换（0,1）和（0,2）（包括）之间的元素，并获得新的排序。这意味着这应该是一个有效的排序，即使它不是因为有一个非常好的解决方案：

(0, 1)          (0, 1)
(1, 3)   -->    (0, 2)
(0, 2)          (1, 3)
(2, 3)          (2, 3)

因此，使用std::sort无法解决这个问题。

我不确定的是解决这个问题的最佳方法是什么。这似乎与流量问题有关，但我不确定如何设置它。如果我想到任何事情，我会更新这个答案。感谢您发布有趣的内容！

Answer 2

我不会为此使用std :: sort。让我解释一下原因。

1）您的排序取决于有关所有要排序的成员的信息，而不是成对比较。在您的示例中，[0,1]之前出现[4,5]的原因是列表中存在[1,4]。如果你在列表中有[5,0]，那么暗示[0,1]会在[4,5]之后出现。更糟糕的是，如果两者都在列表中，那么您没有明确的基础来选择哪个应该首先出现。

2）您的排序方法没有明确定义。例如，你没有解释为什么[0,1]应该出现在[0,2]之前而不是之后。同样，如果你有[[0,1]，[1,2]，[1,3]]，则无法知道[1,2]或[1,3]是否应该是第二个。

另一个重要的考虑因素感觉你可能正在做某种寻路/链接问题。总体而言，您的数据结构可能不太适合您的问题。这只是一个观察，但也许值得考虑。

Answer 3

@ templatetypedef的建议很棒。考虑到这一点后，这听起来更像是一种调度算法，而不是一种排序算法。特别是，它类似于类似于离线调度算法的电梯（即，在运行时调度时所有有序到达都是已知的），其约束条件是任何时候都只能占用一个任务。换句话说，电梯将仅在一个方向上行进，直到它推理出最高要求的楼层为止。一旦到达那里，它将下降到最低请求的楼层并转到下一个请求的顶部。

我假设列表中元素的顺序对应于请求的到达。

这在下图中说明。

如果上述假设为真，则此伪代码如下：

1. Create two helper maps:
2. LeftKeyPairMap containing all tuples (leftValue, Pair) e.g. (0, (0,1)), (0,(0,2)) ...
3. PairIndexMap containing all tuples (Pair, Index) e.g. ((0,1),0), ((0,2),1) ...
4. Initialize an empty schedule
5. Add first input element to schedule and mark it as visited
6. Start input search at index = 1
7. Repeat while schedule size != input list {
8.   lastElementInSchedule = shedule.get(index - 1);
9.   Check if LeftKeyPairMap contains the an entry with key: lastElementInSchedule.rightElem
10.   if (a pair is present and it is not yet marked visited) {
11.      add pair to schedule
12.      mark pair as visited
13.      increment index
14.   } else {
15.     find min univisited index (identified as the non-consecutive gap in visited entries
16.     add the univisited pair to schedule
17.     increment index
18.   }
19. } // End Loop

Answer 4

你不能使用std::sort，因为你的排序不能用严格的弱排序来表达（如T.C.指出）。但是你可以通过一些手工分类功能来做到这一点。像这样的东西：

typedef std::vector<pair<int,int>> PVect
PVect mysort(const PVect& in){
    PVect result;
    // first element is the same ?
    result.push_back(in[0]);
    // add the next one
    for (int i=1;i<in.size();i++){
        if (in[i].second() == result[0].first()){
             result.push_back(in[i]);
        }
    }
    /* ... */
    return result;
}

这段代码肯定不好，但它只是为了引导你朝着正确的方向前进。

Answer 5

您不能使用std::sort()，因为它需要严格的弱排序。我会将矢量复制到std::multi_map，然后按排序顺序将它们放回去：

std::multi_map<int,int> values( vectorOfPairs.begin(), vectorOfPairs.end() );
vectorOfPairs.clear();
for( auto iter = values.begin(); iter != values.end(); ) {
    vectorOfPairs.push_back( *iter );
    values.erase( iter );
    iter = values.find( vectorOfPairs.back().second );
    if( iter == values.end() ) iter = values.begin();
}

Answer 6

如果您从一开始就可以访问完整的完整向量，那么您可以尝试一种选择排序：

1. 扫描完整列表并在开始时选择所需项目并将其交换到位置1。
2. 剩余项目执行时：扫描剩余项目并选择下一个项目并将其交换到下一个位置

这将有效，但其时间复杂度为n平方，因此如果向量非常大，它可能会很慢。

Answer 7

相当晚了。但可能会对某人有所帮助。此代码用于连续订购的对列表。

它将给出以下排序

0, 1
1, 4
4, 5
5, 6

但不是

0, 1
1, 4
4, 5
5, 6
0, 2
2, 3
3, 4

所以，

1. 如果我们有（1,2）我们不应该有（2,1）（1不应再看到）
2. 对列表应该有一个起点和一个终点

我们需要一个起点。我按照以下步骤操作。

1. 创建一个名为originalMap的映射，它将每个对的第一个值存储为键，将第二个值存储为值
2. 创建另一个名为reverseMap的映射，它将每个对的第二个值存储为键，将第一个值存储为值
3. 迭代原始地图：a。如果originalMap中的任何键值也不是rev​​erseMap中的键，那么这就是起点，因为起点不是输入b中任何对的第二个值。如果没有起始点（存在一个周期）或多于一个这样的值，则路径中存在断开连接，我们可以得出结论：不能从给定输入形成连续序列并且会抛出异常
4. 如果找到有效的起始点，则可以从该点迭代原始地图，直到按顺序找到所有对

public static List<Pair<Integer, Integer>> sortSegments (List<Pair<Integer, Integer>> segments){
        LinkedList<Pair<Integer, Integer>> resultList = new LinkedList<Pair<Integer,Integer>>();

        if(segments.size() == 0) return resultList;
        HashMap<Integer, Integer> originalMap = new HashMap<>();
        HashMap<Integer, Integer> reverseMap = new HashMap<>();

        for(Pair<Integer, Integer> segment : segments) originalMap.put(segment.getKey(), segment.getValue());  // original pairs 
        for(Pair<Integer, Integer> segment : segments) reverseMap.put(segment.getValue(), segment.getKey());   // reversed pairs

        System.out.println("The original input order: " + originalMap);
        System.out.println("The reverse order: " + reverseMap);

        List<Integer> startingPoints = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry: originalMap.entrySet()) { // if an element from original is not in reverse then thats 
            if(!reverseMap.containsKey(entry.getKey())) startingPoints.add(entry.getKey()); // the first to go into the output resultList
        }

        Integer pairFirst = null;
        if(startingPoints.size() != 1) {            // if there are multiple / NO starting points are identified then there is no
            throw new IllegalArgumentException("Invalid input segments"); // contiguous path for the segments to be arranged
        } else {
            pairFirst = startingPoints.get(0);
            Integer pairSecond = originalMap.get(pairFirst); 
            while(pairSecond != null) {
                resultList.add(new Pair<Integer, Integer>(pairFirst, pairSecond));
                pairFirst = pairSecond;
                pairSecond = originalMap.get(pairFirst);
            }
        }

        return resultList;
    }