首页 计算机科学 C++

# next_permutation

在 C++ 标准库中， next_permutation 是一个非常实用的函数，它可以用来生成给定序列的下一个字典序排列。这意味着，给定一个序列， next_permutation 能够重新排列其元素，得到一个在所有可能的排列中按字典顺序排在当前排列之后的 “下一个” 排列。如果当前排列已经是所有可能排列中的最后一个，则 next_permutation 会将序列改为最小的排列（即第一个排列），并返回 false ；否则，返回 true 。

next_permutation 定义在头文件 <algorithm> 中，因此使用它之前需要包含这个头文件。

# 函数原型

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);
  • 第一个版本使用 operator< 来比较元素，第二个版本允许用户提供自定义的比较函数 comp 。
  • first 和 last 是双向迭代器，分别指向序列的起始位置和末尾位置的下一个位置。
  • 如果能够将区间内的元素重新排列为下一个字典序排列，则函数返回 true ；如果这些元素已经处于最大的排列，则重新排列为最小的排列，并返回 false 。

# 使用示例

以下示例展示了如何使用 next_permutation 来生成给定序列的所有排列：

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    std::vector<int> vec = {1, 2, 3};
    // 输出 vec 的所有排列
    do {
        for (int num : vec) {
            std::cout << num << " ";
        }
        std::cout << "\n";
    } while (std::next_permutation(vec.begin(), vec.end()));
    return 0;
}
输出：


1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 



在这个例子中， next_permutation  被用来生成并输出序列 {1, 2, 3}  的所有排列。注意，要使得 next_permutation  能够遍历所有可能的排列，初始序列应当处于最小排列状态，即升序排列。在上述代码中，由于初始序列已经是升序排列，因此从第一个排列开始，一直到最后一个排列，每次调用 next_permutation  都会得到下一个排列，直到所有排列都被遍历完毕。


next_permutation  是解决排列组合问题时的一个强大工具，特别是当你需要遍历一个序列的所有排列以寻找特定条件的解时。


# sort


std::sort  是 C++ 标准库中的一个非常重要且常用的算法，定义在头文件 <algorithm>  中。它用于对序列（如数组、向量等容器）进行排序。 std::sort  默认按照升序排列元素，但也可以通过提供自定义的比较函数或者比较对象来指定不同的排序准则。


# 基本用法


#include <algorithm> // 包含 std::sort
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1};
    
    std::sort(vec.begin(), vec.end()); // 默认升序排序
    for(int num : vec) {
        std::cout << num << " ";
    }
    std::cout << "\n";
    return 0;
}
输出：


1 2 3 4 5 



# 自定义排序准则


你可以通过传递第三个参数（比较函数或 Lambda 表达式）给 std::sort  来实现自定义排序准则。例如，以下代码演示了如何降序排序：


#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1};
    
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
        return a > b; // 降序排序
    });
    for(int num : vec) {
        std::cout << num << " ";
    }
    std::cout << "\n";
    return 0;
}
输出：


5 4 3 2 1 



# 注意事项


    

  1. 效率： std::sort  通常实现为快速排序，平均时间复杂度为 O(n log n) ，其中 n  是序列的长度。但标准并未明确规定使用哪种排序算法，因此具体实现可能会有所不同。
    2. 

  2. 稳定性：默认情况下， std::sort  不保证排序的稳定性（即相等元素的相对顺序可能会改变）。如果需要稳定排序，应使用 std::stable_sort 。
    3. 

  3. 自定义比较函数：自定义比较函数需要能够接受两个序列中的元素作为参数，并返回一个布尔值。如果第一个参数应该排在第二个参数之前，则返回 true ；否则返回 false 。
    4. 



# sort&pair


在 C++ 中，使用 std::sort  函数对 pair<int, int>  数组或向量进行排序时， std::sort  默认会首先根据 pair  的第一个元素进行升序排序，如果第一个元素相同，则根据第二个元素进行升序排序。这是因为 std::pair  的比较操作符已经按照这样的规则进行了重载。


以下是一个简单的示例，展示如何使用 std::sort  对 pair<int, int>  的向量进行排序：


#include <algorithm> // std::sort
#include <vector>
#include <iostream>
int main() {
    std::vector<std::pair<int, int>> vec = <!--swig0-->;
    std::sort(vec.begin(), vec.end());
    for(const auto &p : vec) {
        std::cout << "(" << p.first << ", " << p.second << ")" << std::endl;
    }
    return 0;
}
输出结果将是：


(1, 2)
(1, 3)
(2, 2)
(2, 4)
(3, 1)
(3, 3)



# 自定义排序准则


如果你想要自定义排序准则，例如，先按照第二个元素降序排序，如果第二个元素相同，则按照第一个元素升序排序，你可以传递一个自定义的比较函数或 lambda 表达式给 std::sort 。下面是如何实现这一自定义排序准则的示例：


#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<std::pair<int, int>> vec = <!--swig1-->;
    std::sort(vec.begin(), vec.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
        if(a.second != b.second) return a.second > b.second; // 优先按第二个元素降序
        return a.first < b.first; // 第二个元素相同，则按第一个元素升序
    });
    for(const auto &p : vec) {
        std::cout << "(" << p.first << ", " << p.second << ")" << std::endl;
    }
    return 0;
}
这段代码的输出结果将是：


(2, 4)
(3, 3)
(1, 3)
(1, 2)
(2, 2)
(3, 1)



这样，你就可以根据需要对 pair<int, int>  进行自定义排序了。


      

          
      

  


   


    

  
    
      
    
    更新于