排列类

created by Dejavu
(不断更新中)

排列(Permutation)

• 介绍

从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A(n,m）表示。
排列需要考虑到元素顺序，有两种常用方法分别为顺序法，交换法。

• 顺序法就是先固定前n-2位然后依次递减固定位数，直到全部排序完毕,这里以n=4，m=2(4)为例
  

• 交换法就是每次变动时只移动一个数字，一般采用从后向前再从前向后的方法进行排序
  

• 实现

• 顺序法
  void _gen_perm(int *a,int n,int m,int l,int *tmp,int *tag) {
  if(l == m) {
  for(int i=0;i<n-1;i++) cout << a[i] << ' ';
  cout << a[n-1] << endl;
  }
  else for(int i=0;i<n;i++) {
  if(!tag[i]) {
  tmp[l] = a[i], tag[i] = 1;
  _gen_perm(a,n,m,l+1,tmp,tag);
  tag[i] = 0;
  }
  }
  }
  void gen_perm(int n,int m) {
  int a[MAXN],tmp[MAXN],tag[MAXN] = {0};
  for(int i=0;i<n;i++) a[i] = i+1;
  _gen_perm(a,n,m,0,tmp,tag);
  }

• 交换法，只支持全排列
  void _gen_perm_swap(int *a,int n,int l,int *pos,int *dir) {
  int p1,p2,t;
  if(l == m) {
  for(int i=0;i<n-1;i++) cout << a[i] << ' ';
  cout << a[n-1] << endl;
  }
  else {
  _gen_perm_swap(a,n,l+1,pos,dir);
  for(int i=0;i<l;i++) {
  p2 = (p1=pos[l])+dir[l];
  t = a[p1], a[p1] = a[p2], a[p2] = t;
  pos[a[p1]-1] = p1, pos[a[p2]-1] = p2;
  _gen_perm_swap(a,n,l+1,pos,dir);
  }
  dir[l] = -dir[l];
  }
  }
  void gen_perm_swap(int n) {
  int a[MAXN],pos[MAXN],dir[MAXN];
  for(int i=0;i<n;i++) a[i] =i+1, pos[i] = i, dir[i] = -1;
  _gen_perm_swap(a,n,0,pos,dir);
  }