C++全排列的详解

一、递归求解全排列

全排列的一个常见求解方法是使用递归算法，其主要思想是将问题划分成一个个子问题，逐步求解，最后组合得到结果。

下面是使用递归算法求解全排列的示例代码。

#include <iostream>
#include <algorithm>
using namespace std;

void permutation(char* str, int start, int end) {
    if(start == end) {
        cout << str << endl;
    } else {
        for(int i = start; i <= end; i++) {
            swap(str[start], str[i]);
            permutation(str, start + 1, end);
            swap(str[start], str[i]);
        }
    }
}

int main() {
    char str[] = "abc";
    int len = sizeof(str) / sizeof(char) - 1;
    sort(str, str + len);
    permutation(str, 0, len - 1);
    return 0;
}

在上述代码中，permutation 函数使用了递归的方法，遍历每一个为起始下标的字符，并交换该下标和其他下标的字符，以求得全排列。

二、基于STL的全排列

C++的STL库提供了许多方便快捷的算法，其中就包括了全排列算法。使用STL库的全排列算法，可以使程序更加简洁和高效。

下面是使用STL库的全排列算法的示例代码。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    char str[] = "abc";
    int len = sizeof(str) / sizeof(char) - 1;
    sort(str, str + len);
    do {
        cout << str << endl;
    } while(next_permutation(str, str + len));
    return 0;
}

在上述代码中，next_permutation 函数使用了STL库的全排列算法，不需要用户实现递归，只需遍历每一个排列即可。同时，使用STL库函数可以充分发掘C++语言的优势，简化编码过程。

三、性能比较

一般而言，自己写的算法之所以比STL库函数实现的慢，其主要原因在于STL库函数有一些额外的开销。

下面是使用不同算法求解同一个全排列问题的运行时间对比。

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

void permutation(char* str, int start, int end) {
    if(start == end) {
        cout << str << endl;
    } else {
        for(int i = start; i <= end; i++) {
            swap(str[start], str[i]);
            permutation(str, start + 1, end);
            swap(str[start], str[i]);
        }
    }
}

int main() {
    char str[] = "abcd";
    int len = sizeof(str) / sizeof(char) - 1;

    clock_t t1 = clock();
    sort(str, str + len);
    permutation(str, 0, len - 1);
    clock_t t2 = clock();
    cout << "递归解法花费的时间: " << t2 - t1 << "ms" << endl;

    t1 = clock();
    sort(str, str + len);
    do {
        cout << str << endl;
    } while(next_permutation(str, str + len));
    t2 = clock();
    cout << "STL库函数解法花费的时间: " << t2 - t1 << "ms" << endl;

    return 0;
}

在上述代码中，使用了计算时间的函数 clock()。在这个例子中，递归解法的时间复杂度为 n!，STL库函数的时间复杂度为 n! * logn，但是从实际测试中可以看出，STL库函数比递归解法要快很多，因此可见使用STL库函数来解决问题，其恰当性和高效性是值得肯定的。