根据值对的自定义排序向量

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

你不能使用std::sort，因为你的排序不能用严格的弱排序来表达（如T.C.pointed）。但是，您可以通过一些手工排序功能来完成。像这样：

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 2

您可以将此问题视为图形问题。你的每一对代表有向图中的一条边。例如，对 (0, 2) 表示 "there's an edge from node 0 to node 2," 而对 (2, 5) 表示 "there's an edge from node 2 to node 5."

如果您这样想，每对的第二个元素与下一对的第一个元素匹配的一系列边对应于图中的一条路径。例如，您给出的排序顺序中有两条路径：0 -> 1 -> 4 -> 5 -> 6 和 0 -> 2 -> 3 -> 4。因此，你要解决的问题求解如下：如何将图中的边分解为最少数量的边不相交路径？一旦你解决了这个问题，你就可以输出这些路径在任何order 你想按照你想做的事情形成一个排序。

你无法用 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) 是不可比的。这意味着在任何排序顺序中，(0, 1) 和 (0, 2)（含）之间的所有元素也必须是不可比较的，因为 transitivity of incomparability。换句话说，我们应该能够进行任何排序，置换 (0, 1) 和 (0, 2)（含）之间的元素，并获得新的排序。这意味着这应该是一个有效的排序，即使它不是因为有一个更好的解决方案：

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

所以没有办法用std::sort来解决这个问题。

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

Answer 3

您不能使用 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 4

我不会为此使用 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] 应该是第二个。

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

Answer 5

@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 6

如果您从一开始就可以访问完整的向量，您可以尝试一种select离子排序：

扫描完整列表和 select 您想要的项目，然后将其交换到位置 1。
剩下的项目：扫描剩余的项目和select你想要的下一个并将其交换到下一个位置

这可行，但它的时间复杂度是 n 的平方，因此如果向量非常大，它可能会很慢。

Answer 7

很晚了 post。但可能会帮助某人。此代码用于连续排序的成对列表。

它会给出以下排序

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

但不是

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

所以，

如果我们有 (1,2) 我们不应该有 (2,1) （1 不应该再次出现）
一对列表应该有一个起点和一个终点

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

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

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;
    }

根据值对的自定义排序向量

Custom sort vector of pair based on their values

c++

vector

std-pair