全排列问题

从n个不同元素中任取m（m ≤ n）个元素，按照一定的顺序排列起来，叫做从 n 个不同元素中取出 m 个元素的一个排列。当m = n时所有的排列情况叫全排列。

以下举例 1,2,3,4,5 的全排列解决方案；

1.for循环解决——直接循环，保证数字不一样即可；

#include <iostream> 

using namespace std; 

void Full(int * a,int n) { 
    for(int k1 = 0;k1 < n;k1++) { 
        for(int k2 = 0;k2 < n;k2++) { 
            if(k1 != k2) // ....... 
        } 
    } 
} 

int main() 
{ 
    int a[5] = {1,2,3,4,5};
    Full(a,5); 
    return 0; 
}

2.next_permutation()——可以查一下这个函数，下面实现全排列；

#include <iostream>
#include <algorithm>

using namespace std;

void Full_next(int * a,int n) {
    sort(a,a+n);
    do {
        for(int i = 0;i < n;i++)
            cout << a[i] << " ";
        cout << endl;
    }while(next_permutation(a,a + n));
}

int main()
{
    int a[5] = {1,2,3,4,5};
    Full_next(a,5);
    return 0;
} 

3.递归实现——加一点dfs思想，利用深度确定递归出口；

#include <iostream>

using namespace std;

void Swap(int & x,int & y) {
    int temp = x;
    x = y;
    y = temp;
}

void Print(int * a,int n) {
    for(int i = 0;i < n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}

void Full_dfs(int * a,int n,int i) {
    if(i >= n)
        Print(a,n);
    else {
        for(int j = i;j < n;j++) {
            Swap(a[i],a[j]);
            Full_dfs(a,n,i + 1);
            Swap(a[j],a[i]); 
        } 
    }
}

int main()
{
    int a[5] = {1,2,3,4,5};
    Full_dfs(a,5,0);
    return 0;
}