生成排列

排列的概念
排列，一般地，从n个不同元素中取出m（m≤n）个元素，按照一定的顺序排成一列，叫做从n个元素中取出m个元素的一个排列(permutation)。特别地，当m=n时，这个排列被称作全排列(all permutation)。
排列数p(n,r)=n!/(n-r)!,p(n,n)=n!,0!=1
从1-3中取2个元素的排列为{1，2}，{1，3}，{2，1}，{2，3}，{3，1}，{3，2}共计6种。
从a-c的全排列为{abc}，{acb}，{bac}，{bca}，{cab}，{cba}共计6种。
生成排列算法
一、最简单的方法，直接使用STL中的next_permutation函数生成排列。

#include 
using namespace std;
int main()
{
    char res[] = "ABCD";
    do{
        puts(res);
    }while(next_permutation(res, res+4));
    return 0;
}

二、：采用递归的思想解决，先输出所有以A开头的排列，然后输出以B开头的排列，接着输出...，最后输出以N开头的排列。以A开头的排列中，第一位是A，后面是B~N的排列。以AB开头的排列中，第一位是A，第二位是B，后面是C~N的排列......如此递归，生成的是按照字典序排列的全排列。

#include 
using namespace std;
int n;
char table[] = "ABCDEFGHIJK";
char res[1024];
void solve(int cur)
{
    if(cur == n){
        res[cur] = 0;
        puts(res);
        return ;
    }
    for(int i = 0; i < n; i++){
        bool ok = true;
        for(int j = 0; j < cur; j++)
            if(table[i] == res[j])
                ok = false;
        if(ok){
            res[cur] = table[i];
            solve(cur+1);
        }
    }
}
int main()
{
    while(cin >> n)
        solve(0);
    return 0;
}

方法三：应该算是回溯法，这种方法效率应该最高。
首先选择在首位元素，分别A~N，选择方法是与第一位后面的元素交换，然后选择第二位元素，选择方法是与第二位后面的元素交换，如此递归进行......注意递归返回时要把交换过的变量交换回来。

#include 
using namespace std;
int n;
char res[] = "ABC";
void solve(int cur)
{
    if(cur == n){
        res[cur] = 0;
        puts(res);
        return ;
    }
    for(int j = cur; j < n; j++){
        swap(res[j], res[cur]);
        solve(cur+1);
        swap(res[j], res[cur]);
    }
}
int main()
{
    n = strlen(res);
    solve(0);
    return 0;
}

方法四：带标记的递归方法。这种方法递归排列是要记录下之前访问过的字母，避免了产生排列生成下一个字母时对前面的搜索避免的时间浪费。依然要注意标记要在递归返回时修改。

#include 
using namespace std;
int n;
char table[] = "ABCD";
char res[1024];
bool vis[1024];
void solve(int cur)
{
    if(cur == n){
        res[cur] = 0;
        puts(res);
        return ;
    }
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            res[cur] = table[i];
            vis[i] = true;
            solve(cur+1);
            vis[i] = false;
        }
    }
}
int main()
{
    n = strlen(table);
    memset(vis, false, sizeof(vis));
    solve(0);
    return 0;
}