C++中字符串全排列算法及next_permutation原理详解

介绍

全排列是指将一组数按一定顺序进行排列，得到所有有可能的组合。例如，对于数字1、2、3，全排列如下：

123
132
213
231
312
321

C++中有现成的函数next_permutation可以实现全排列，但理解其原理仍然很重要，本篇文章将详细讲解next_permutation的原理以及如何在代码中实现字符串的全排列。

next_permutation原理

next_permutation函数是C++标准库algorithm头文件中的函数。该函数通过对当前序列进行重新排序，使其变为下一个更大的排列，如果下一个更大的排列存在，则函数返回true，否则返回false。下面是next_permutation函数的语法：

bool next_permutation(first, last, cmp)

其中，first和last定义了需要进行排列的序列，cmp可选，表示自定义的比较函数。默认情况下，next_permutation使用小于号运算符进行比较。

使用next_permutation的时候，需要先将序列进行排序，升序或降序都可以，排完序之后再重复调用该函数即可得到全排列。

下面是next_permutation的伪代码实现：

bool next_permutation(first, last)
{
    if (first == last) // 只有一个元素
        return false;

    auto i = last - 1;
    while (i != first && *(i - 1) >= *i) // 从后往前找到第一个左邻小于右邻的元素
        --i;

    if (i == first) // 已经是最大排列
        return false;

    auto j = last - 1;
    while (*j <= *(i - 1)) // 从后往前找到第一个大于i-1位置元素的元素
        --j;

    std::swap(*(i - 1), *j); // 交换i-1和j位置的元素

    std::reverse(i, last); // 翻转i位置到最后一个元素的序列

    return true;
}

字符串全排列示例

下面来看一个字符串全排列的示例，例如我们将字符串”abc”进行全排列。

首先按字典序排序，”abc”小于”acb”，因此先输出“abc”，然后对字符序列进行重排得到”acb”。

然后继续比较，”acb”小于”bac”，因此接着输出”acb”，并重排为”bac”。

以此类推，最后输出”cba”。

下面是字符串全排列的C++代码实现：

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

int main()
{
    std::string str = "abc";
    std::sort(str.begin(), str.end()); // 将字符串排序
    do {
        std::cout << str << std::endl; // 打印当前排列
    } while (std::next_permutation(str.begin(), str.end())); // 重排得到下一个排列，直到最后一个排列
    return 0;
}

输出：

abc
acb
bac
bca
cab
cba

复杂度分析

next_permutation的时间复杂度为O(n)，其中n为序列中元素的个数，因此字符串的全排列的时间复杂度为O(n!)。排列数量很大时需要注意时间复杂度问题。

总结

本文介绍了next_permutation的原理以及如何实现字符串全排列。学会使用next_permutation函数可以很方便地得到一个序列的全排列，理解其原理也可以帮助我们更好地理解C++中的STL。