C++ 算法 next_permutation ()

2025年1月12日 | 阅读 4 分钟

C++ 算法 next_permutation() 函数用于将范围 [first, last) 中的元素重新排序为下一个按字典序更大的排列。

排列 (permutation) 定义为一组事物或数字可以被排序或排列的几种可能方式中的每一种。它表示为 N!，其中 N = 范围中的元素数量。

对于第一个版本，使用运算符 < 比较元素，或者对于第二个版本，使用给定的二元比较函数 comp 比较元素。

语法

default (1)    template <class BidirectionalIterator>
         bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

custom (2)    template <class BidirectionalIterator, class Compare>
                     bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, 
                                                              Compare comp);

参数

first：一个双向迭代器，指向要进行排列的范围中的第一个元素。

last：一个输入迭代器，指向要进行排列的范围中最后一个元素之后的位置。

comp：一个用户定义的二元谓词函数，它接受两个参数，如果这两个参数有序则返回 true，否则返回 false。它遵循严格弱序来对元素进行排序。

返回值

如果函数可以将对象重新排序为按字典序更大的排列，则返回 true。

否则，函数返回 false，表示排列不大于前一个排列，而是最低可能的排列（按升序排序）。

复杂度

复杂度最高为 first 和 last 之间距离的一半的线性复杂度。

数据竞争

范围 [first, last) 中的对象会被修改。

异常

如果元素被交换或迭代器操作引发异常，则此函数会引发异常。

注意：无效参数会导致未定义行为。

示例 1

让我们看一个简单的示例来演示 next_permutation() 的用法

#include <algorithm>
#include <string>
#include <iostream>

using namespace std;
 
int main()
{
    string s = "aba";
    sort(s.begin(), s.end());
    do {
        cout << s << '\n';
    } while(next_permutation(s.begin(), s.end()));
    
    return 0;
}

输出

aab
aba 
baa

示例 2

让我们看另一个简单示例

#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

using namespace std;

int main () {
  int myints[] = {1,2,3};

  sort (myints,myints+3);

  cout << "The 3! possible permutations with 3 elements:\n";
  do {
    cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( next_permutation(myints,myints+3) );

  cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

输出

The 3! possible permutations with 3 elements:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
After loop: 1 2 3

示例 3

让我们看另一个简单示例

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin)
                {
                        reverse(begin, end);
                        return false;
                }
        }
}

int main()
{
        vector<int> v = { 1, 2, 3, 4 };

        do
        {
                for (int i = 0; i < 4; i++)
                {
                        cout << v[i] << " ";
                }
                cout << endl;
        }
        while (::next_permutation(v.begin(), v.end()));
}

输出

示例 4

让我们看一个简单的例子

#include <iostream>
#include <algorithm>

using namespace std;

// Program to find all lexicographically next permutations
int main()
{
    string s = "231";
    
    // Optional: sort the string in natural order before calling
    // std::next_permutation inside a loop to print all permutations,
    // not just the ones that follows specified string lexicographically

    // std::sort(begin(s), end(s));

    // find all lexicographically next permutations using 
    // std::next_permutation
    while (1)
    {
        // print current permutation
        cout << s << " ";

        // find next permutation in lexicographic order
        if (!next_permutation(begin(s), end(s)))
            break;
    }

    return 0;
}

输出

231 312 321

下一主题Java stringbuilder length 方法

C++ 算法 next_permutation ()

语法

参数

返回值

复杂度

数据竞争

异常

注意：无效参数会导致未定义行为。

示例 1

示例 2

示例 3

示例 4

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 算法 next_permutation ()

语法

参数

返回值

复杂度

数据竞争

异常

注意：无效参数会导致未定义行为。

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm for_each() 函数

algorithm fill_n() 函数

algorithm unique() 函数

algorithm is_permutation() 函数

algorithm reverse_copy() 函数

algorithm find_first_of() 函数

algorithm binary_search() 函数

algorithm partition_copy() 函数

algorithm partial_sort() 函数