组合数学$3 排列组合生成算法

组合数学$3 排列组合生成算法"/>

组合数学$3 排列组合生成算法

C3 排列组合生成算法

String 近似公式： n ! ∼ 2 π n ( n e ) n n! \sim \sqrt{2\pi n}(\frac{n}{e})^n n!∼2πn ​(en​)n

S1 排列生成

-1）随机法：

• 取数法
• 洗牌法

0）递归生成：从 n − 1 n-1 n−1 的排列生成

1）Even 全排列算法：

• 执行：

  1. 每个数上方标一个左右箭头，若指向一个较小的数，称该数可移动
  2. 从 1 , 2 , ⋯   , n 1,2,\cdots,n 1,2,⋯,n 开始，所有箭头向左
  3. 找到最大可移动数 k k k，移动 k k k 并把大于 k k k 的数的箭头转向

• 算法生成的顺序与递归生成法一致

• 实际上可以确定 Even 算法的第 k k k (以 0 0 0 开始)个排列：

  数 n n n 的位置： k = n ⋅ q n + r n k = n\cdot q_n+r_n k=n⋅qn​+rn​，

  若 q n q_n qn​ 为偶数，则在左起第 r n + 1 r_n+1 rn​+1 个空位

  若 q n q_n qn​ 为奇数，则在右起第 r n + 1 r_n+1 rn​+1 个空位

  依次填写 n , n − 1 , ⋯   , 1 n,n-1,\cdots,1 n,n−1,⋯,1的位置即可

$$1,2,3 \vert \vec{3},2,1 \
1,3,2 \vert 2,\vec{3},1 \
3,1,2 \vert 2,1,\vec{3} \$$

$$1,2,\dot{3} \vert \dot{3},2,1 \
1,\dot{3},2 \vert 2,\dot{3},1 \
\dot{3},1,2 \vert 2,1,\dot{3} \$$

2）逆序生成排列：

• 逆序列： { b n } , b i \{b_n\},b_i {bn​},bi​ 表示数 i i i 的逆序数

• 生成：

  • 方式一：从 n n n 写到 1 1 1：数 k k k 写在已写好的 b n − k