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);
}
