一）ss2365:全排列问题
题目描述
输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。(注意输出格式（p老师的恶意）)
输入 n(1<=n<=9)
输出 由1~n组成的所有不重复的数字序列，每一行一个序列，每个数字前4个空格。
样例输入 3
样例输出
    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

#include "bits/stdc++.h"
void dfs(int k){ 这是全排列的題解。这里所要全排列的是数字i。不过，除了示例以外，真正做題时，不会出i。把这个i理解成，某种数组组合的下标i，通用性就广了。stl::next_permutation就是针对这样的用途。
using namespace std;
int main()
{
    char str[7];
    cin>>str;
    int len=strlen(str);
    do{
        for(int i=0;i
        cout<<str[i];
        cout<<endl;
    }while(next_permutation(str,str+len));
    return 0;
}

1)P127.5.1.7也是全排列完成程序，(交换完成回溯)；
2)P133.5.2.3也是全排列，但主要考察，根据伪代码，修正得出可行的程序；

二）coj1032/ss2362:组合的输出
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素（不分顺序且r<=n），我们可以简单地将n个元素理解位自然数1，2，…，n，从中任取r个数。
现要求你用递归的方法输出所有组合。
例如 n=5，r=3，所有组合为：
1 2 3    1 2 4    1 2 5    1 3 4    1 3 5    1 4 5    2 3 4    2 3 5    2 4 5    3 4 5
输入  一行两个自然数n、r(1<=r<=n)。
输出
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。
样例输入 5 3
样例输出
  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5
#include "bits/stdc++.h"
using namespace std;
int a[101]={1};//注意这里，与课本例題不一样，但效果一样
bool p[101];
int n,r,cnt;
void dfs(int k){
    if(k>=r+1){
        for(int i=1;i<=r;i++) cout<<a[i]<<" ";
        cout<<endl;
        cnt++;
    }else

        for(int i=a[k-1];i<=n;i++)//
            if(p[i]){//
                p[i]=false;//
                a[k]=i;//
                dfs(k+1);
                a[k]=0;
                p[i]=true;
                }
    }
int main(){
    memset(p,true,sizeof(p));
    cin>>n>>r;
    dfs(1);
}

三）部分排列 P136.5.2.7
设有n个整数的集合｛1,2,…,n｝，从中取出任意r个数进行排列（r < n），试列出所有的排列。
using namespace std;
int num=0,a[10001]={0},n,r;
bool b[10001]={0};
int search(int);                                      //回溯过程
int print();                                              //输出方案

int main()
{
  cout<<"input n,r:";
  cin>>n>>r;
  search(1);
  cout<<"number="<<num<<endl;     //输出方案总数
}

int search(int k)
{
    int i;
    for (i=1;i<=n;i++)//对比上题，由于没有限定从i=a[k-1]起步，所以输出成“部分排列”
     if  (!b[i])                                 //判断i是否可用
      {
         a[k]=i;                               //保存结果
         b[i]=1;
         if (k==r) print();
            else search(k+1);
         b[i]=0;
      }
}
int print()
{
  num++;
  for (int i=1;i<=r;i++)
    cout<<setw(3)<<a[i];
  cout<<endl;
}


四）ss2359:有重复元素的排列问题
设R=｛r1,r2,…，rn}是要进行排列的n个元素。其中元素r1,r2,…，rn可能相同。试设计一个算法，统计R的所有不同排列的总数。
给定n以及待排列的n个元素。计算这n个元素的所有不同排列。
输入
输入两行，第一行是元素个数n，1<=n<=500。接下来的一行是待排列的n个元素（小写字母）。
输出 输出所有的排列方案（按字典序排序），每个一行，最后一行输出排列总数
样例输入
4
aacc
样例输出
aacc
acac
acca
caac
caca
ccaa
6
这道題是有重复元素的全排列问題。真的考试，会出这种題目，楼上的題目，只配拿来初赛填充。
不过，其实可以用比较简单的办法，完成这道題。比如说，用全排列，然后剔除其中重复的值即可。
STL的map可以完成这个任务，set st;也可以完成同样的任务。
因为本质上都是全排列，所以时间上不会有什么差别。
现在说的是从“理解全排列的角度”，去说这道題。
下面是pascal代码 (c-f)
var a:array['a'..'z'] of longint;
    i,n,tot:longint;
    ch:char;
    c:array[1..500] of char;
procedure dfs(i:longint);
var j:char;
    k:longint;
begin
 for j:='a' to 'z' do//按Ascii码检查桶排序后的哈希表，把记录下来的字母作为排序对象，一个个用完。
     if a[j]>0 then//发现这个字母仍然可用（原始串含，或不止一个）
         begin
          a[j]:=a[j]-1;//消耗一个字母
          c[i]:=j;
         if i < n then dfs(i+1)
          else
            begin
              tot:=tot+1;
              for k:=1 to n do write(c[k]);//输出结果
              writeln;
            end;
          a[j]:=a[j]+1;//复原
         end;
end;
begin
  readln(n);
  for i:=1 to n do
     begin
        read(ch);//读入原始串
        a[ch]:=a[ch]+1;//桶排序，作为深搜回溯的依据；
     end;
  dfs(1);//这是指从'a'开始搜，但是起码字母不一定是a，从尽可能优化的角度，可以用while搜索到第一个出现的字母，再开始搜。不过，这只对大数据量有用，而小数据量时，无须考虑时间性能。
  writeln(tot);
end.

#include "bits/stdc++.h"
using namespace std;
 
int ans,n,j;
char l[501];
int a[150];
 
void find(int x,int k)
{
        if(x>n){
            ans++;
            for(int i=1;i<=n;i++) printf("%c",char(l[i]));printf("\n");;
        }
        else 
        {
            for(int i=k;i<='z';i++)
                if(a[i]>0)
                {
                    l[x]=i;
                    a[i]--;
                    if (! a[k]) find(x+1,k+1);
                    else find(x+1,'a');
                    a[i]++;
                    }  
            }
    }
 
int main(){
    cin>>n;cin>>l;
    for(int i=0;i < n;i++) a[l[i]]++;
    int k=97;
    while(! a[k]) k++;
    find(1,k);
    cout<<ans<<endl;
    }
    

对比两題的全排列，原理一样，区别只是用于排列的“原始串材料不一样，来源不一样”，然后相应地处理。

五) 474.排列
考虑一些序列。这些序列满足以下条件：
(1)序列的长度是u
(2)序列的元素是1~9范围内的数字
(3)同一个序列的元素没有重复
把满足上述条件的单个序列，定义为“排列”
现有两个排列，用两个数字来说明这两个排列的一致性。其中，第一个数是两个排列中位置相同，且数值也相同的数字的总和，而另一个数字则是都出现在两个排列中，但位置不相同的数字的总和。
现有u个排列，并且已知它们同某个未知的排列的一致性的具体数据，要求出未知的排列。

输入数据
第1行１个正整数u,1<=u<=9
接下来的u行，描述所给的数字排列和它们与要求的未知排列的一致性，每一行这样的描述，由u+2个用１个空格隔开的正整数表示。第1和第2个数字是评价该排列与未知排列的一致性。最后u个数字是由数字1~9构成的一个排列。
输出数据
输出一行包含u个不同的数字。表示要求的未知排列，这些数字由１～９构成，且相邻两数之间严格用一个空隔分开。对于输入数据至少有一种解法。如果对于输入数据来说，存在多个合适的排列，程序应该定出其中的任意一个。

样例输入
3
4 0 4 9 7
0 10 6 7 4
0 5 9 4 1
样例输出
4 1 6

样例解释：
4 9 7 与4 1 6，相同且位置相同的数的和4,相同但位置不同的数的和是0
6 7 4 与4 1 6，相同且位置相同的数的和0,相同但位置不同的数的和是10
9 4 1 与4 1 6，相同且位置相同的数的和0,相同但位置不同的数的和是5

输入样例一
1
0 0 5
输出样例一
１

输入样例二
4
0 9 5 1 4 8
2 7 4 6 7 2
0 3 1 6 2 4
0 8 3 4 7 1
输出样例二
7 8 1 2

输入样例三
5
0 6 2 6 3 5 9
0 13 8 1 4 2 3
0 5 2 5 4 1 3
0 16 8 9 7 3 1
1 11 2 5 1 4 7
输出样例三
4 7 1 8 6

题目分析：
该题的核心是“排列”：在９个数字中，选取n个的排列。
所以它的核心是一个求排列数的dfs;
不过，这个dfs的退出条件，相当复杂：需要每一个数，检查在各组数中，是否满足题目所要求的位置相同而数量相同，位置相同不相同而和相同，这两个条件。 所以可以单独写成一个检测函数check(i)[i:1..9]，更进一步，还可以把每个i[1..9]的检测，（里面是求和和对比），也写成函数。
这题的真正难点不是DFS，而是如何判断
第一个数是两个排列中位置相同，且数值也相同的数字的总和，而另一个数字则是都出现在两个排列中，但位置不相同的数字的总和。

可以用一个arr[i][j]存储每一行数，j本身包含了位置；
再用in[i][arr[i][j]]对arr[i][j]作桶排序；
在递归求得排列结果的时侯，会有一个保存当前搜索结果的now[],它的位置就是当前枚举的数字组合的位置；
因此 now[j]==arr[行][j]就体现了是否位置相同；（满足了第一个求和条件）
如果位置不相同　!=　的话，结合桶排序in[][]，就可以满足第二个求和条件。
using namespace std;
const int N = 20;
int n, dis[N][2], arr[N][N], now[N], h[N], in[N][N];

int isValid(int id) {