created by Dejavu
(不斷更新中)
排列(Permutation)
- 介紹
從n個(gè)不同元素中，任取m(m≤n,m與n均為自然數(shù),下同）個(gè)元素按照一定的順序排成一列这敬，叫做從n個(gè)不同元素中取出m個(gè)元素的一個(gè)排列筝闹；從n個(gè)不同元素中取出m(m≤n）個(gè)元素的所有排列的個(gè)數(shù)媳叨，叫做從n個(gè)不同元素中取出m個(gè)元素的排列數(shù)，用符號(hào) A(n,m）表示关顷。
排列需要考慮到元素順序糊秆，有兩種常用方法分別為順序法解寝，交換法艘儒。
-
順序法就是先固定前n-2位然后依次遞減固定位數(shù)，直到全部排序完畢,這里以n=4界睁，m=2(4)為例
-
交換法就是每次變動(dòng)時(shí)只移動(dòng)一個(gè)數(shù)字，一般采用從后向前再?gòu)那跋蚝蟮姆椒ㄟM(jìn)行排序
實(shí)現(xiàn)
順序法
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);
}
