[笔记] C++中全排列枚举的几种实现方式

[笔记] C++中全排列枚举的几种实现方式

 1.DFS（使用递归与回溯实现）

对于普通数组Array，这里给出函数模板形式：

#include
using namespace std;

template
void func(T* arr, int total, int k = 0)    //轮流更换第n位和n到total-1位
{
    for (int i = k; i < total; i++)
    {
        if (k == total - 1)    //在此对排列好的数组进行下一步操作
        {
            for (int p = 0; p < total; p++)cout << arr[p];
            cout << "n";
            return;
        }
        {T t = arr[i]; arr[i] = arr[k]; arr[k] = t; }//swap(a[k],a[i]);
        func(arr, total, k + 1);
        {T t = arr[i]; arr[i] = arr[k]; arr[k] = t; }
    }
}

int main()
{
    int arr[]{ 1,2,3,4,5 };
    func(arr, 5);

    char crr[] = "ABCDEFG";
    func(crr, 4);

    return 0;
}

对于字符串，则可跳过回溯步骤，相应地，空间复杂度将由O(1)提升至O( n! )，具体实现如下：

#include
using namespace std;

void f(string& str, int n = 0)
{
    if (n == str.size() - 1)cout << str << endl;        //在此对排列好的数组进行下一步操作
    for (int i = n; i < str.size(); ++i)
    {
        string ts = str;
        auto t = ts[i];
        ts[i] = ts[n];
        ts[n] = t;
        f(ts, n + 1);
    }
}

int main()
{
    return 0;
    string str = "1234567890";
    f(str);

    return 0;
}

2.调用 algorithm.h 中的next_permutation ()函数

伪代码如下：

do {

   // todo

} while (next_permutation(a, a + n));

其中a为数组首地址，n为数组大小；

对于string或vector，在参数中传入首末迭代器即可。