设R={r1,r2,…,rn}是要进行排列的n个元素,R的全排列记为perm(R),Ri=R-{ri},(ri)perm(Ri)表示集合Ri的全排列中每个排列前增加一个前缀所形成的所有排列。于是
当n=1时,perm(R)=(r),其中r是R中的唯一元素;
当n>1时,perm(R)由(r1)perm(R1), (r2)perm(R2),…,(rn)perm(Rn)构成。
求R的全排列的解决思路之一是:
1. 给排列中的每个元素均赋予一个向左或向右的箭头。
2. 如果元素k的箭头指向的是与其相邻但小于k的元素,则称元素k是活动的。
3. 从排列 1 2 3 … n 开始,找其中的最大活动元素k,将该元素k与它所指向的相邻元素交换位置,并改变所有大于k的元素的方向。
2022-01-12 16:53:10
10KB
全排列算法
1